文章目录[x]
- 1:原题链接:
- 2:题意:
- 3:思路:
- 3.1:所以:
- 4:参考代码:
csdn博客链接:https://blog.csdn.net/nuoyanli/article/details/105407577
原题链接:
http://poj.org/problem?id=1184
题意:
通过给定的六种操作将一个六位数变为另一个六位数,求需要的最少操作数。
六种操作:
左移和右移:将光标位置左移一位或右移一位,在第一位时无法左移,最后一位时无法右移。
左交换和右交换:将光标位置的数字与第一位或最后一位交换
增大和减小:将光标位置的数字增大或减小
思路:
- 刚开始的时候没想到搜索,在想着如何贪心,考虑最优的选择得到最少操作数,但是发现没有类似最优子结构的东西,也就不能了。
- 于是想到了,搜索(也就是),就是考虑从初始状态到达最终状态嘛,就是状态可达的性质,也是最小操作数,但是直接这样显然空间时间都是有问题的,因为有个位置*个不同的数=个状态,所以必须考虑剪枝:
- 我们不难知道,这六种操作对一个数只有两种影响,一种是交换两个数位的位置,另一种是改变某个数位的值。
- 所以,当且仅当光标到达某一数位,对这一数位的值的改变才可能发生。所以全部操作可分为两种:一种是移位和交换操作,一种是增大和减小操作。
所以:
考虑到这两种交换操作都不涉及到位置,所以这几个位置只能通过来改变。
如果这几个位置是和目标状态是不一样的,那肯定是用操作是最优的,而不会执行操作,也就是上面说的,只有这几个位置在和目标状态一样时才做操作。
这样剪枝之后,就可以直接搜索了:用字符串存下数字,并把光标位置当做一个字符加到末尾,用标记当前状态是否出现过,然后即可。
参考代码:
// nuoyanli
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
//#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define kB kush_back
#define FI first
#define SE second
//#define in
#define RI register
#define PB push_back
#define m_k(a, b) make_kair(a, b)
#define debug(a) cout << "---" << a << "---" << endl
#define debug_(a, b) cout << a << "---" << b << endl
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 2e6 + 10;
const int M = 1e3 + 10;
const LL mod = 1e9 + 9;
const LL inf = 0x3f3f3f3f;
const double f = 2.32349;
struct node {
int step;
string s;
} str;
string en;
map<string, int> mmp;
queue<node> q;
int bfs() {
node t, tt;
string temp;
q.push(str);
mmp[str.s] = 1;
while (!q.empty()) {
t = q.front();
q.pop();
if ((t.s).substr(0, 6) == en) {
return t.step;
}
temp = t.s;
swap(temp[0], temp[temp[6] - '0']); // S0
if (!mmp.count(temp)) {
tt.s = temp;
tt.step = t.step + 1;
q.push(tt);
mmp[temp] = 1;
}
temp = t.s;
swap(temp[5], temp[temp[6] - '0']); // S1
if (!mmp.count(temp)) {
tt.s = temp;
tt.step = t.step + 1;
q.push(tt);
mmp[temp] = 1;
}
temp = t.s;
if (temp[temp[6] - '0'] != '9' &&
temp[temp[6] - '0'] != en[temp[6] - '0']) {
temp[temp[6] - '0'] += 1; // U
}
if (!mmp[temp]) {
tt.s = temp;
tt.step = t.step + 1;
q.push(tt);
mmp[temp] = 1;
}
temp = t.s;
if (temp[temp[6] - '0'] != '0' &&
temp[temp[6] - '0'] != en[temp[6] - '0']) {
temp[temp[6] - '0'] -= 1; // D
}
if (!mmp[temp]) {
tt.s = temp;
tt.step = t.step + 1;
q.push(tt);
mmp[temp] = 1;
}
temp = t.s;
if (temp[6] != '0') { // L
if (temp[6] != '5') {
if (temp[temp[6] - '0'] == en[temp[6] - '0']) {
temp[6] -= 1;
}
} else {
temp[6] -= 1;
}
}
if (!mmp[temp]) {
tt.s = temp;
tt.step = t.step + 1;
q.push(tt);
mmp[temp] = 1;
}
temp = t.s;
if (temp[6] != '5') { // R
if (temp[6] != '0') {
if (temp[temp[6] - '0'] == en[temp[6] - '0']) {
temp[6] += 1;
}
} else {
temp[6] += 1;
}
}
if (!mmp[temp]) {
tt.s = temp;
tt.step = t.step + 1;
q.push(tt);
mmp[temp] = 1;
}
}
}
void solve() {
IOS;
cin >> str.s >> en;
mmp.clear();
str.s = str.s + '0';
str.step = 0;
cout << bfs() << endl;
}
signed main() {
#ifdef in
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
solve();
return 0;
}