题解 P1225 【黑白棋游戏】
此题的关键点：
1.状态转换：由于只有01，并且二进制对应的十进制的值是唯一的，因此可以考虑将数组使用对应的十进制来进行保存，如此一来，判重也很容易实现。（因为最大的数是二进制16个1，也就是2^16-1，不会超空间）
2.搜索策略：任何一种状态都需要从16个位置作为起点开始进行扩展，扩展后合法的子状态全部加入队列中，再从队列中取出队首值进行扩展，当然同样需要把这个队首值从16个位置均考虑作为起点开始扩展，获取到的所有合法的子状态......
3.记录结果：由于判重的原因，每一个数的父节点必然是唯一的，因此可从终点（目标状态）出发，往前找其父节点的值并保存，记录当前的节点坐标和父节点的坐标，输出的时候就可以从终点不断往前面推出路径。
4.处理结果：通过（3）处理得到的结果是从终点出发的，当然可以通过简单的代码操作实现输出正解。
细节较多，需要细致写代码（要敢于动手），代码注释中有关键步骤的解释，可参考代码理解以上思路。
#include<bits/stdc++.h>
using namespace std;
char c;
int csz,mbz,cnt,a[5][5],b[5][5],vis[65540],father[65540],res[100000][4];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct Ans{
int nx,ny,ox,oy,father;
}ans[100000];
queue<int>q;
//初始化输入起点和目标点
void init(){
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>c;
a[i][j]=c-'0';
}
}
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>c;
b[i][j]=c-'0';
}
}
}
//获取4*4数组二进制得到十进制数
int getDeci(int a[5][5]){
int comb=0,cnt=0;
for(int i=4;i>=1;i--){
for(int j=4;j>=1;j--){
comb+=a[i][j]*pow(2,cnt);
cnt++;
}
}
return comb;
}
//根据x修改a数组的值
void updateArr(int x,int a[5][5]){
while(x){
for(int i=4;i>=1;i--){
for(int j=4;j>=1;j--){
a[i][j]=x%2;
x/=2;
}
}
}
}
//判断是否越界且父子值要不同
bool legal(int ox,int oy,int nx,int ny){
if(nx>=1&&nx<=4&&ny>=1&&ny<=4&&a[ox][oy]!=a[nx][ny])
return true;
else return false;
}
void bfs(){
q.push(csz);//从初始值开始扩展
vis[csz]=1;
while(!q.empty()){
int exted=q.front(); //exted用来存储每次被扩展的数
updateArr(exted,a); //将a数组修改为当前被扩展的数对应的二进制
q.pop();
for(int i=1;i<=4;i++){ //每一种状态的数都要分别以它的十六个点为起点来进行扩展
for(int j=1;j<=4;j++){
int ox=i,oy=j;
for(int k=0;k<4;k++){
int nx=ox+dx[k],ny=oy+dy[k];
//标记是否有执行swap，以决定是否需要再次执行swap还原a数组状态
int flag=0;
if(legal(ox,oy,nx,ny)){
flag=1;
int fdeci=getDeci(a); //当前被扩展的值（当前被扩展出来的节点的父节点的值）
swap(a[ox][oy],a[nx][ny]);
int deci=getDeci(a); //swap后的a数组对应的十进制值
if(!vis[deci]){
vis[deci]=1;
ans[deci].father=fdeci; //存储路径
ans[deci].nx=nx,ans[deci].ny=ny;
ans[deci].ox=ox,ans[deci].oy=oy;
father[deci]=fdeci;
q.push(deci);
}
if(deci==mbz) //扩展得到了目标节点
return;
}
if(flag) //需要还原a数组状态
swap(a[ox][oy],a[nx][ny]);
}
}
}
}
}
int main(){
init();
csz=getDeci(a),mbz=getDeci(b);//csz：初始值，mbz：目标值
bfs();
father[csz]=0;
while(father[mbz]){ //从目标节点往前推路径并存储到res数组中
cnt++;
res[cnt][0]=ans[mbz].ox,res[cnt][1]=ans[mbz].oy,res[cnt][2]=ans[mbz].nx,res[cnt][3]=ans[mbz].ny,
mbz=father[mbz];
}
cout<<cnt<<endl;
for(int i=cnt;i>=1;i--) //从起点--->终点的交换过程
cout<<res[i][0]<<res[i][1]<<res[i][2]<<res[i][3]<<endl;
return 0;
}代码仅供一种思路参考（不要抄袭，没有任何意义），能够写出来AC的同学可尝试进一步使用双向bfs进行优化。