题目
Description
三行三列的数组，其元素值为0至8的数。现有如下的变换规则：
1： 将0与上面一行元素对换
2：将0与下面一行元素对换
3：将0与左面一行元素对换
4：将0与右面一行元素对换
如果已知一个三行三列元素的初始情况，问最少需几次变换，能变换为指定的一种情况？
1： 将0与上面一行元素对换
2：将0与下面一行元素对换
3：将0与左面一行元素对换
4：将0与右面一行元素对换
如果已知一个三行三列元素的初始情况，问最少需几次变换，能变换为指定的一种情况？
Input
包括六行的数据，每行有三个以空格分隔的数字。 前三行为原始状态 后三行为目标状态
Output
若能在20次以内（包括20）变换得到目标状态的数组,输出最少的变换次数;
若不能在20次以内（包括20）变换得到目标状态的数组，输出No solution!
若不能在20次以内（包括20）变换得到目标状态的数组，输出No solution!
Sample Input
0 4 8
2 6 3
1 7 5
0 2 3
1 8 4
7 6 5
Sample Output
10
解题思路：
也就是暴力去搜索，暴力查看当前状态是否与目标状态一致；
枚举假设的答案，看是否满足条件，如果满足在假设交换次数的情况下能到达目标状态，那么假设的答案就是正解；
所以可以从1-20去枚举假设的交换次数，我们只需验证答案即可；
但暴力铁定是过不了的，所以需要优化；
优化思路：
假设当前状态为
0 1 2
3 4 5
6 7 8
目标状态为
1 2 0
3 4 5
6 7 8
那么最理想的交换次数就是3次，也就是比较目标状态与当前状态 有多少个不一样的数字；
这样就可以得出从当前状态到目标状态的最少交换次数，也是最理想的交换次数；
然鹅，并不是所有当前状态到目标状态的最少交换次数都是 求有多少个不一样的数字；
如：
当前状态
0 1 2
3 4 5
6 7 8
目标状态
7 1 2
3 4 5
0 8 6
很显然这个当前状态达到目标状态，肯定是大于最理想的交换次数的，但绝不会小于最理想的交换次数；
所以我们可以利用这个定性来优化，也就是如果 当前交换的次数+最理想的交换次数>假设的交换次数
那么说明我们假设的这个答案不满足条件，那么重新在假设一个交换次数进行验证
渣渣代码（包涵注释）
#include<bits/stdc++.h> int ans[4][4],a[4][4],flag,k; int bx[4]={0,1,-1,0}; int by[4]={1,0,0,-1}; using namespace std; int check() { for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(ans[i][j]!=a[i][j])return 0;//查看当前状态是否与目标状态一致 return 1; } int test(int step)//理想状态的优化，上面题解说明中给出 { int t=0; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(ans[i][j]!=a[i][j]) { if(++t+step>k) return 0;} return 1; } void A_star(int step,int x,int y,int pre) { if(step==k){ if(check())flag=1; return;}//如果假设的答案变换次数内可以到达目标状态， //flag=1 说明找到答案 if(flag) return; //如果找到答案了就返回 if(step>k)return;//如果变换的次数超过，假设的答案，那么也返回 if(step>20)return;//超过题目给的界限，返回 for(int i=0;i<4;i++)//枚举每次变换的方向 { int nx=x+bx[i],ny=y+by[i];//记录与0交换的位置 if(nx<1||nx>3||ny<1||ny>3||pre+i==3)//不越界 且 不走回头路 //如 by[0]=1,by[3]=-1,by[0]+by[3]=0, //说明当前状态 0 3 交换成后 3 0，又会交换成 0 3 ，我们要防止这种情况 continue; swap(a[x][y],a[nx][ny]);//交换 if(test(step)&&!flag)//如果没有找到答案并且可以往下找 A_star(step+1,nx,ny,i); swap(a[x][y],a[nx][ny]);//回溯 } } int main() { int x,y; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { cin>>a[i][j]; if(a[i][j]==0) x=i,y=j;//记录下0在那个位置 } for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) cin>>ans[i][j];//将目标状态 输入 if(check()){cout<<0;return 0;}//如果目标状态与原始状态相等，就不需变换了 while(++k) {//枚举假设每个答案 k A_star(0,x,y,-1); if(k>20){cout<<"No solution!";return 0;} if(flag){cout<<k;break;}//如果假设的答案成立，就输出 } return 0; }