BFS+Cantor
#include <bits/stdc++.h> #include <queue> using namespace std; const int maxn = 362880; int start[9]; int goal[9] = { 1,2,3,4,5,6,7,8,0 }; int factory[10]; bool visit[maxn]; int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} }; char weizhi[4] = { 'u','l','d','r' }; struct node { int state[9]; string step; }; queue<node>q; bool Cantor(int arr[9]) { long temp = 0; for (int i = 0; i < 9; i++) { int count = 0; for (int j = i + 1; j < 9; j++) { if (arr[j] > arr[i]) { count++; } } temp += count * factory[9 - 1 - i]; } if (visit[temp] == false) { visit[temp] = true; return true; } else { return false; } } string bfs() { node head; memcpy(head.state, start, sizeof(head.state)); head.step = ""; q.push(head); Cantor(head.state); while (!q.empty()) { node temp = q.front(); q.pop(); int index = 0; for (int i = 0; i < 9; i++) { if (temp.state[i] == 0) { index = i; break; } } int x = index / 3; int y = index % 3; for (int i = 0; i < 4; i++) { int newx = x + dir[i][0]; int newy = y + dir[i][1]; if (newx >= 0 && newx <= 2 && newy >= 0 && newy <= 2) { node newnode; newnode.step = temp.step + weizhi[i]; //memcpy(&newnode, &temp, sizeof(struct node)); memcpy(newnode.state, temp.state, sizeof(newnode.state)); swap(newnode.state[index], newnode.state[newx*3+ newy]); if (memcmp(newnode.state, goal, sizeof(goal)) == 0) { return newnode.step; } if (Cantor(newnode.state) == true) { q.push(newnode); } } } } return "unsolvable"; } int main() { char num; factory[0] = 1; for (int i = 1; i <=9; i++) { factory[i] = factory[i - 1]*i; // cout << factory[i] << endl; } for (int i = 0; i < 9; i++) { cin >> num; if (num == 'x'){ start[i] = 0; } else { start[i] = num - '0'; } //cout << start[i] << " "; } string s = bfs(); cout << s; }