1 #include<cstdio> 2 #include<queue> 3 #include<set> 4 #include<algorithm> 5 using namespace std; 6 const int di[]={0,0,-1,1},dj[]={-1,1,0,0}; 7 struct Squ{char S[4][4];}; 8 struct Node{Squ v;int d;Node(const Squ &a,const int &b){v=a;d=b;}Node(){}}; 9 bool operator < (const Squ &a,const Squ &b)10 {11     for(int i=0;i<4;i++)12       for(int j=0;j<4;j++)13         if(a.S[i][j]<b.S[i][j])14           return true;15         else if(a.S[i][j]>b.S[i][j])16           return false;17     return false;18 }19 bool operator == (const Squ &a,const Squ &b)20 {21     for(int i=0;i<4;i++)22       for(int j=0;j<4;j++)23         if(a.S[i][j]!=b.S[i][j])24           return false;25     return true;26 }27 Squ from,to;28 set<Squ>Set;29 queue<Node>q;30 inline bool check(const int &x,const int &y)31 {32     if(x>=0&&x<4&&y>=0&&y<4&&q.front().v.S[x][y]==‘0‘)33       return true;34     return false;35 }36 inline void work(const Squ &tmp)37 {38     if(Set.find(tmp)==Set.end())39       {40           if(tmp==to)41             {42                 printf("%d\n",q.front().d+1);43                 exit(0);44             }45           Set.insert(tmp);46           q.push(Node(tmp,q.front().d+1));47       }48 }49 int main()50 {51     for(int i=0;i<4;i++)scanf("%s",from.S[i]);52     for(int i=0;i<4;i++)scanf("%s",to.S[i]);53     if(from==to){printf("0\n");return 0;}54     q.push(Node(from,0));55     Set.insert(from);56     while(!q.empty())57       {58           for(int i=0;i<4;i++)59             for(int j=0;j<4;j++)60               if(q.front().v.S[i][j]==‘1‘)61                 {62                     for(int k=0;k<4;k++)63                       {64                           int ti=i+di[k],tj=j+dj[k];65                           if(check(ti,tj))66                             {67                                 Squ tmp=q.front().v;68                                 swap(tmp.S[i][j],tmp.S[ti][tj]);69                                 work(tmp);70                             }71                       }72                 }73           q.pop();74       }75     return 0;76 }