- #include#include#define N 500000 using namespace std;
- struct node {
- int mp[4][4];
- }
- a[N];
- int g[4][4] = {
- {
- 0,
- 0,
- 0,
- 0
- },
- {
- 0,
- 1,
- 2,
- 3
- },
- {
- 0,
- 8,
- 0,
- 4
- },
- {
- 0,
- 7,
- 6,
- 5
- }
- };
- int xx[4] = {
- 0,
- 0,
- 1,
- -1
- };
- int yy[4] = {
- 1,
- -1,
- 0,
- 0
- };
- int hash[3733800];
- int step[N];
- int h,
- t = 1,
- flag;
- int check() {
- for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) if (a[t].mp[i][j] != g[i][j]) return 0;
- return 1;
- }
- int Hash() {
- int s = 0,
- k = 1;
- for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) s += a[t].mp[i][j] * k,
- k *= 7;
- s %= 3733799;
- if (!hash[s]) {
- hash[s] = 1;
- return 1;
- }
- return 0;
- }
- int pd(int x, int y) {
- if (x && x <= 3 && y && y <= 3) return 1;
- return 0;
- }
- void move(int x, int y) {
- for (int i = 0; i < 4; i++) {
- int p = x + xx[i],
- q = y + yy[i];
- if (pd(p, q)) {
- for (int j = 1; j <= 3; j++) for (int k = 1; k <= 3; k++) a[t].mp[j][k] = a[h].mp[j][k];
- swap(a[t].mp[x][y], a[t].mp[p][q]);
- step[t] = step[h] + 1;
- if (check()) {
- cout < 1;
- return;
- }
- if (Hash()) t++;
- }
- }
- }
- void search() {
- while (h < t) {
- for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) {
- if (a[h].mp[i][j] == 0) move(i, j);
- if (flag) return;
- }
- h++;
- }
- }
- int main() {
- string str;
- cin >> str;
- for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) a[0].mp[i][j] = str[(i - 1) * 3 + j - 1] - '0';
- search();
- }
来源: http://www.bubuko.com/infodetail-1950628.html