题解 P2578 【[ZJOI2005]九数码游戏】
进一步强化广搜，增强代码能力的较好练习题。
思路上和八数码/魔板等题类似，每次一个状态按照两种方式进行扩展，使用队列存储每一种状态，直到弹出的状态是目标状态则结束。几个关键点：
1.输入的是3*3的矩阵，按照数组存储后，可以转换成9位数来表示状态。
2.两种操作，自行模拟下处理过程即可。
void move1(int a[4][4]){ //操作一
int tmp=a[1][1];
a[1][1]=a[2][1],a[2][1]=a[3][1],a[3][1]=a[3][2];
a[3][2]=a[3][3],a[3][3]=a[2][3],a[2][3]=a[1][3],a[1][3]=a[1][2],a[1][2]=tmp;
}
void move2(int a[4][4]){ //操作二
int tmp=a[2][3];
a[2][3]=a[2][2],a[2][2]=a[2][1],a[2][1]=tmp;
}3.判重：此处如果用普通的数组来存储九位数作为下标判重当然是会超出空间，使用map的方法来进行判重会TLE五个点，因此这里使用的康托展开的方式获取每一种状态（每一个九位数）唯一映射的数字作为数组下标，这样是不会超空间的，因为九位数的全排列的可能性也就是9的阶乘。（不了解康托展开的同学可百度详细了解）
4.输出路径，可以使用数组来保存每一种状态的前驱是谁。（从后往前，想想为什么）
具体过程看代码，注释写的很详细，代码比较长，细细看清楚每个函数的功能应该是可以很容易看懂代码，之后再自行实现即可。
#include<bits/stdc++.h>
using namespace std;
int cs[4][4],a[4][4],b[4][4],vis[1000000],mb=12345678,cnt,csz;
long long ans[100000];
map<long long,long long>father; //用于存路径
void init();
void bfs();
long long getDec(int a[4][4]);
void updateArr(long long s,int a[4][4]);
int getCantor(long long tmp);
void move1(int a[4][4]);
void move2(int a[4][4]);
void print(long long x);
int getCantor(long long tmp) //根据九位数字获取对应的康托展开值
{
int a[9]={0},i=8,ans=0;
while(tmp!=0){
a[i]=tmp%10;
tmp/=10;
i--;
}
for(i=0;i<9;i++)
{
int x=0;int c=1,m=1;
for(int j=i+1;j<9;j++)
{
if(a[j]<a[i])x++;
m*=c;c++;
}
ans+=x*m;
}
return ans;
}
void print(long long x){ //将数字按照3*3的数组的形式输出
updateArr(x,a);
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
long long getDec(int a[4][4]){ //3*3数组转化成对应的数字
long long s=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
s=s*10+a[i][j];
return s;
}
void updateArr(long long s,int a[4][4]){ //使用数字来更新修改a数组的值
for(int i=3;i>=1;i--){
for(int j=3;j>=1;j--){
a[i][j]=s%10;
s/=10;
}
}
}
void move1(int a[4][4]){ //操作一
int tmp=a[1][1];
a[1][1]=a[2][1],a[2][1]=a[3][1],a[3][1]=a[3][2];
a[3][2]=a[3][3],a[3][3]=a[2][3],a[2][3]=a[1][3],a[1][3]=a[1][2],a[1][2]=tmp;
}
void move2(int a[4][4]){ //操作二
int tmp=a[2][3];
a[2][3]=a[2][2],a[2][2]=a[2][1],a[2][1]=tmp;
}
void init(){ //处理输入
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
cin>>cs[i][j];
csz=getDec(cs);
}
void bfs(){
queue<long long>q;
q.push(csz);
while(!q.empty()){
long long exted=q.front();
q.pop();
if(exted==mb) //找到了目标
return;
updateArr(exted,a); //根据此次拓展的结点更新a数组的值
memcpy(b,a,sizeof(a));//复制一个a数组：b数组，方便做两种操作（就不需要做完一种操作后恢复）
long long fa_a=getDec(a),fa_b=getDec(b);//得到a、b数组没操作前对应的数值
move1(a),move2(b); //分别用a、b数组做两种操作
long long son_a=getDec(a),son_b=getDec(b);//得到a、b数组操作后对应的数值
int cantor_a=getCantor(son_a),cantor_b=getCantor(son_b);//得到操作后的数值的康托展开式
if(!vis[cantor_a]) //判重：是否出现过
q.push(son_a),vis[cantor_a]=1,father[son_a]=fa_a; //使用father数组来记录路径
if(!vis[cantor_b])
q.push(son_b),vis[cantor_b]=1,father[son_b]=fa_b;
}
}
int main(){
init();
csz=getDec(cs); //csz：初始值
bfs();
father[csz]=0;
long long tmp=mb; //mb：目标
while(father[tmp]){ //如此找到的是倒过来的顺序，所以使用ans数组将结果存一遍
cnt++;
tmp=father[tmp];
ans[cnt]=tmp;
}
if(!cnt){
cout<<"UNSOLVABLE"<<endl;
return 0;
}
cout<<cnt<<endl;
for(int i=cnt;i>=1;i--){ //将ans数组倒着输出一遍，即得到从起点到终点的次序
print(ans[i]);
}
print(mb);
return 0;
}