1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 using namespace std; 5   6 //#define __debug 7 #ifdef __debug 8     #define Function(type) type 9     #define Procedure      void10 #else11     #define Function(type) __attribute__((optimize("-O2"))) inline type12     #define Procedure      __attribute__((optimize("-O2"))) inline void13 #endif14  15 Function(int) encode(bool map[4][4])16 {17     int ret=0;18     range(i,0,4) range(j,0,4)19     {20         (ret<<=1)+=map[i][j];21     }22     return ret;23 }24 Procedure decode(25     const int&status,bool map[4][4]26 )27 {28     int S=status;29     dange(i,3,-1) dange(j,3,-1)30     {31         map[i][j]=S&1,S>>=1;32     }33 }34  35 static const int dx[4]={ 1,-1, 0, 0};36 static const int dy[4]={ 0, 0, 1,-1};37 bool ST[4][4],ED[4][4],tmp[4][4];38 queue< pair<int,int> > que;39 bitset<65536> vis;40 Procedure extend(41     const int&x,const int&y,const int&s42 )43 {44     range(i,0,4)45     {46         int tx=x+dx[i],ty=y+dy[i];47         if(~tx&&~ty&&tx<4&&ty<4&&!tmp[tx][ty])48         {49             tmp[x][y]=0,tmp[tx][ty]=1;50             int status=encode(tmp);51             if(!vis.test(status))52             {53                 que.push(make_pair(status,s));54                 vis.set(status);55             }56             tmp[x][y]=1,tmp[tx][ty]=0;57         }58     }59 }60 Function(int) BFS()61 {62     int init=encode(ST),zone=encode(ED);63     que.push(make_pair(init,0));64     vis.set(init);65     for(;!que.empty();que.pop())66     {67         int status=que.front().first ,68             steps =que.front().second;69         if(status==zone) return steps;70         decode(status,tmp);71         range(i,0,4) range(j,0,4)72         {73             if(tmp[i][j]) extend(i,j,steps+1);74         }75     }76 }77  78 int main()79 {80     range(i,0,4) range(j,0,4)81     {82         char c;83         while(!isdigit(c=getchar()));84         ST[i][j]=c-‘0‘;85     }86     range(i,0,4) range(j,0,4)87     {88         char c;89         while(!isdigit(c=getchar()));90         ED[i][j]=c-‘0‘;91     }92     return printf("%d\n",BFS()),0;93 }