有限制条件的广搜，判重的数组（或其他东西）一定，要，是K维的啊啊啊啊啊啊……
也就是，这个状态由多少个参数决定，判重数组就要是多少维的。包括预处理的时候，待查找的数组也要是多少维的。
这个好像之前有博客里写过……背思修大概背傻了。
例题：What a ridiculous election?
描述
In country Light Tower, a presidential election is going on. There aretwo candidates, Mr. X1andMr. X2, and both of them are not like good persons. One is called aliar and the other is called a maniac. They tear(Chinese English word, meansdefame) each other on TV face to face, on newspaper, on internet…on allkinds of media. The country is tore into two parts because the people whosupport X1are almost as many as the people who support X2.
After the election day, X1and X2get almost thesame number of votes. No one gets enough votes to win. According to the law ofthe country, the Great Judge must decide who will be the president. But thejudge doesn’t want to offend half population of the country, so he randomlychooses a 6 years old kid Tom and authorize him to pick the president. Soundsweird? But the democracy in Light Tower is just like that.
The poor or lucky little kid Tom doesn’t understand what is happening tohis country. But he has his way to do his job. Tom’s ao shu(Chinese Englishword, means some kind of weird math for kids) teacher just left him a puzzle afew days ago, Tom decide that he who solve that puzzle in a better way will bepresident. The ao shu teacher’s puzzle is like this:
Given a string which consists of five digits(‘0’-‘9’), like"02943", you should change “12345” into it by as few aspossible operations. There are 3 kinds of operations:
-
Swap two adjacent digits.
-
Increase a digit by one. If the result exceed 9, change it to it modulo10.
-
Double a digit. If the result exceed 9, change it to it modulo 10.
You can use operation 2 at most three times, and use operation 3 at mosttwice.
As a melon eater(Chinese English again, means bystander), whichcandidate do you support? Please help him solve the puzzle.
输入
There are no more than 100,000 test cases.
Each test case is a string which consists of 5 digits.
输出
For each case,print the minimum number of operations must be used to change “12345” into the given string. If there is no solution, print -1.
样例输入
12435
99999
12374
样例输出
1
-1
3
错误代码嗯我不怕丢人引以为戒：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
int visited[100003];
struct state {
int num;
int op2;
int op3;
int opnum;
state () {}
state (int _num, int _op2, int _op3, int _opnum): num(_num), op2(_op2), op3(_op3), opnum(_opnum) {}
};
int op1(int num, int pos) {
char cur[10];
sprintf(cur, "%05d", num);
char tmp = cur[pos];
cur[pos] = cur[pos + 1];
cur[pos + 1] = tmp;
int ret = atoi(cur);
return ret;
}
int op2(int num, int pos) {
char cur[10];
sprintf(cur, "%05d", num);
int tmp = cur[pos] - '0';
tmp = (tmp + 1) % 10;
cur[pos] = char(tmp + '0');
int ret = atoi(cur);
return ret;
}
int op3(int num, int pos) {
char cur[10];
sprintf(cur, "%05d", num);
int tmp = cur[pos] - '0';
tmp = (tmp * 2) % 10;
cur[pos] = char(tmp + '0');
int ret = atoi(cur);
return ret;
}
int main() {
queue <state> Q;
map <int, int> S;
char input[10];
Q.push(state(12345, 0, 0, 0));
visited[12345] = 1;
S.insert(make_pair(12345, 0));
state cur;
while (!Q.empty()) {
cur = Q.front();
Q.pop();
if (cur.op3 < 2) {
for (int i = 0; i < 5; ++i) {
int newnum = op3(cur.num, i);
if (visited[newnum]) continue;
visited[newnum] = 1;
S.insert(make_pair(newnum, cur.opnum + 1));
Q.push(state(newnum, cur.op2, cur.op3 + 1, cur.opnum + 1));
}
}
if (cur.op2 < 3) {
for (int i = 0; i < 5; ++i) {
int newnum = op2(cur.num, i);
if (visited[newnum]) continue;
visited[newnum] = 1;
S.insert(make_pair(newnum, cur.opnum + 1));
Q.push(state(newnum, cur.op2 + 1, cur.op3, cur.opnum + 1));
}
}
for (int i = 0; i < 4; ++i) {
int newnum = op1(cur.num, i);
if (visited[newnum]) continue;
visited[newnum] = 1;
S.insert(make_pair(newnum, cur.opnum + 1));
Q.push(state(newnum, cur.op2, cur.op3, cur.opnum + 1));
}
}
while (cin >> input) {
typename map <int, int>::iterator it = S.find(atoi(input));
if (it == S.end()) cout << -1 << endl;
else cout << it->second << endl;
}
return 0;
}
AC代码（抄了答案的（捂脸）不然根本发现不了……）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const int INF = 100003;
int visited[100003][4][3];
struct state {
int num;
int op2;
int op3;
int opnum;
state () {}
state (int _num, int _op2, int _op3, int _opnum): num(_num), op2(_op2), op3(_op3), opnum(_opnum) {}
};
int op1(int num, int pos) {
char cur[10];
sprintf(cur, "%05d", num);
char tmp = cur[pos];
cur[pos] = cur[pos + 1];
cur[pos + 1] = tmp;
int ret = atoi(cur);
return ret;
}
int op2(int num, int pos) {
char cur[10];
sprintf(cur, "%05d", num);
int tmp = cur[pos] - '0';
tmp = (tmp + 1) % 10;
cur[pos] = char(tmp + '0');
int ret = atoi(cur);
return ret;
}
int op3(int num, int pos) {
char cur[10];
sprintf(cur, "%05d", num);
int tmp = cur[pos] - '0';
tmp = (tmp * 2) % 10;
cur[pos] = char(tmp + '0');
int ret = atoi(cur);
return ret;
}
int main() {
for (int i = 0; i < INF; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 3; ++k) {
visited[i][j][k] = INF;
}
}
}
queue <state> Q;
map <int, int> S;
char input[10];
Q.push(state(12345, 0, 0, 0));
visited[12345][0][0] = 0;
S.insert(make_pair(12345, 0));
state cur;
while (!Q.empty()) {
cur = Q.front();
Q.pop();
if (cur.op3 < 2) {
for (int i = 0; i < 5; ++i) {
int newnum = op3(cur.num, i);
if (visited[newnum][cur.op2][cur.op3 + 1] != INF) continue;
visited[newnum][cur.op2][cur.op3 + 1] = cur.opnum + 1;
//S.insert(make_pair(newnum, cur.opnum + 1));
Q.push(state(newnum, cur.op2, cur.op3 + 1, cur.opnum + 1));
}
}
if (cur.op2 < 3) {
for (int i = 0; i < 5; ++i) {
int newnum = op2(cur.num, i);
if (visited[newnum][cur.op2 + 1][cur.op3] != INF) continue;
visited[newnum][cur.op2 + 1][cur.op3] = cur.opnum + 1;
//S.insert(make_pair(newnum, cur.opnum + 1));
Q.push(state(newnum, cur.op2 + 1, cur.op3, cur.opnum + 1));
}
}
for (int i = 0; i < 4; ++i) {
int newnum = op1(cur.num, i);
if (visited[newnum][cur.op2][cur.op3] != INF) continue;
visited[newnum][cur.op2][cur.op3] = cur.opnum + 1;
//S.insert(make_pair(newnum, cur.opnum + 1));
Q.push(state(newnum, cur.op2, cur.op3, cur.opnum + 1));
}
}
while (cin >> input) {
int ans = INF;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 3; ++j) {
ans = min(ans, visited[atoi(input)][i][j]);
}
}
if (ans == INF) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}