看见很多dalao写了什么双向BFS，蒟蒻表示不会写啊。

怎么办办？

先来分析一下题目，一眼看去就是一个搜索题，考虑DFS与BFS。

先放一份DFS的代码：

#include
    
     using namespace std;bool a[5][5],b[5][5];char c;int dx[5]={0,0,0,1,-1};int dy[5]={0,1,-1,0,0};int ans=0x3f3f3f3f;int ax[110],bx[110],ay[110],by[110];int ansx1[110],ansx2[110],ansy1[110],ansy2[110];int cnt=0,ans_cnt;map
     
      mp;inline string get(){    string s="";    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)s+=a[i][j]+'0';    return s;}inline bool check(){    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)            if(a[i][j]!=b[i][j])return 0;    return 1;}inline void DFS(int x,int y,int tot){    /*for(int i=1;i<=4;i++)    {        for(int j=1;j<=4;j++)cout<
      
       =ans)return;    if(check())    {        ans=tot;        ans_cnt=cnt;        for(int i=1;i<=cnt;i++)        {            ansx1[i]=ax[i];            ansx2[i]=bx[i];            ansy1[i]=ay[i];            ansy2[i]=by[i];        }    }    if(y==5)return;    if(x==5)x=1,y++;    /*string s=get();    cout<
       <
        
         4||bb<1||bb>4||a[aa][bb]==a[x][y])continue;        cnt++;        ax[cnt]=x;ay[cnt]=y;        bx[cnt]=aa;by[cnt]=bb;        swap(a[aa][bb],a[x][y]);        DFS(x+1,y,tot+1);        cnt--;        swap(a[aa][bb],a[x][y]);    }}int main(){    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)        {            cin>>c;            if(c=='1')a[i][j]=1;            else a[i][j]=0;        }    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)        {            cin>>c;            if(c=='1')b[i][j]=1;            else b[i][j]=0;        }    DFS(1,1,0);    cout<
         
          <
         
        
      
     
    

这里枚举每一个点，进行上下左右的交换。看上去很(fei)有(chang)道(che)理(dan)的样子，但是很明显，有时候交换完下面的点还可以去交换上面的点，所以有时候会搜不到答案，只能拿到60分

蓝题能拿60分也很不错了呢

怎么办办？

那么当然要用BFS啦，（蒟蒻不会记录方案的好办法，只能暴力存储啦）

#include
    
     using namespace std;bool a[5][5],b[5][5];char c;int dx[5]={0,0,0,1,-1};int dy[5]={0,1,-1,0,0};//上下左右int ans=0x3f3f3f3f;int ansx1[100],ansx2[100],ansy1[100],ansy2[100];map
     
      mp;//剪枝专用struct Node{    bool cc[5][5];//记录当前局势    int tot;//记录总数    int x1[20],x2[20],y1[20],y2[20];//记录方案};inline void BFS(){    queue
      
       q;    Node now;    now.tot=0;    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)            now.cc[i][j]=a[i][j];//把局势copy一份    q.push(now);    while(q.size())    {        Node now=q.front();        /*for(int i=1;i<=4;i++)        {            for(int j=1;j<=4;j++)cout<
       
        4||bb>4||now.cc[i][j]==now.cc[aa][bb])continue;//超过边界或为相同数字，那么就continue                    swap(next.cc[aa][bb],next.cc[i][j]);//交换                    next.x1[next.tot]=i;next.y1[next.tot]=j;                    next.x2[next.tot]=aa;next.y2[next.tot]=bb;//添加新方案                    q.push(next);                    swap(next.cc[aa][bb],next.cc[i][j]);//回溯                }            }        }    }}int main(){    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)        {            cin>>c;            if(c=='1')a[i][j]=1;            else a[i][j]=0;        }    for(int i=1;i<=4;i++)        for(int j=1;j<=4;j++)        {            cin>>c;            if(c=='1')b[i][j]=1;            else b[i][j]=0;        }    BFS();    cout<
        
         <