问题：很经典的搜索，给定一个3*3的方格，里面放1-8个数字，有一个空格，空位可以与相邻的数字可以移到空格中，问给定一个状态，怎么移动到一个特定的状态（比如1-8顺序存放）。
康拓展开记录当前的状态，BFS即可。
HDU 1043是让给定多组状态，怎么还原成1-8顺序存放，可以倒叙BFS，打标出所有状态，
POJ 1077是一组数据，直接正向搜索即可。
思考：A*怎么解决这道题？
POJ - 1077
#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 1e6 + 111;
int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};int cantor(int s[]){int sum = 0;for(int i = 0;i < 9;++i){int num = 0;for(int j = i+1;j<9;++j){if(s[j] < s[i])num++;}sum += (num*fac[9-i-1]);}return sum + 1;
}struct node{int s[9];int loc;//0的位置、int status;
};struct node1{int pre;char way;
}ns[maxn];int mv[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
char indexs[5] = "udlr";//正向搜索int aim = 46234;node ncur;
bool vis[maxn];
bool bfs(){memset(vis,false,sizeof vis);node cur,nxt;queue<node>q;q.push(ncur);while(q.size()){cur = q.front();q.pop();if(cur.status == aim){return true;}int x = cur.loc/3;int y = cur.loc%3;for(int i = 0;i<4;++i){int tx = x + mv[i][0];int ty = y + mv[i][1];if(tx<0 || tx > 2 || ty < 0 || ty >2)continue;nxt = cur;nxt.loc = tx*3+ty;nxt.s[cur.loc] = nxt.s[nxt.loc];//原来0位置放入现在0位置的数nxt.s[nxt.loc] = 0;//现在放0nxt.status = cantor(nxt.s);if(!vis[nxt.status]){vis[nxt.status] = true;ns[nxt.status].pre = cur.status;ns[nxt.status].way = indexs[i];if(nxt.status == aim){return true;}q.push(nxt);} }}return false;}void print(int x){if(x == ncur.status)return;print(ns[x].pre);cout << ns[x].way;
}
int main(){char ch;while(cin>>ch){if(ch == 'x')ncur.s[0] = 0,ncur.loc = 0;else ncur.s[0] = ch-'0';for(int i = 1;i<9;++i){cin >> ch;if(ch == 'x') ncur.s[i] = 0, ncur.loc = i;else ncur.s[i] = ch-'0';}ncur.status = cantor(ncur.s);if(bfs()){print(aim);}else puts("unsolveable");}
}
HDU - 1043
#include<bits/stdc++.h>using namespace std;const int maxn = 4e5;int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展开判重
bool vis[maxn];
string path[maxn];int cantor(int s[]){int sum = 0;for(int i = 0;i<9;++i){int num = 0;for(int j = i+1;j<9;++j)if(s[j] < s[i])num++;sum += num*fac[9-i-1];}return sum+1;
}struct node{int s[9];//s[i] = j,i在j处int loc;//0 的位置int status;vector<char> path;
};struct node1{int pre;char way;
}ns[maxn];int Move[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
char index[5] = "durl";
int aim = 46234;void bfs()
{memset(vis,false,sizeof vis);node cur,nxt;for(int i = 0;i<8;++i) cur.s[i] = i+1;cur.s[8] = 0;cur.loc = 8;cur.status = aim;ns[aim].pre = -1;queue<node>q;q.push(cur);vis[cur.status] = true;while(q.size()){cur = q.front();q.pop();int x = cur.loc / 3;int y = cur.loc % 3;for(int i = 0;i<4;++i){int tx = x + Move[i][0];int ty = y + Move[i][1];if(tx < 0 || tx > 2 || ty < 0 || ty > 2)continue;nxt = cur;nxt.loc = tx*3 + ty;//0的新位置nxt.s[cur.loc] = nxt.s[nxt.loc];//0的老位置放入0新位置的数nxt.s[nxt.loc] = 0;//新位置更新0nxt.status = cantor(nxt.s);if(!vis[nxt.status]){vis[nxt.status] = true;q.push(nxt);ns[nxt.status].pre = cur.status;ns[nxt.status].way = index[i];}}}}int main()
{char ch;node cur;bfs();while(cin >> ch){if(ch == 'x')cur.s[0] = 0,cur.loc = 0;else cur.s[0] = ch - '0';for(int i = 1;i<9;++i){cin >> ch;if(ch == 'x'){cur.s[i] = 0;cur.loc = i;}else cur.s[i] = ch - '0';}cur.status = cantor(cur.s);if(vis[cur.status]){int status = cur.status;while(ns[status].pre != -1){cout << ns[status].way;status = ns[status].pre;}cout << endl;}else puts("unsolvable");}}