C++ :

#include <cstdio>
#include <queue>
#include <cstring>
#define res register
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int maxn=5,maxb=1<<17;
 
struct Node{
    int step;
    char s[5][5];
    Node(){}
    Node(char ss[5][5],int st){
        for(res int i=1;i<=4;++i)strcpy(s[i]+1,ss[i]+1);step=st;
    }
};
 
int ans;
char s1[maxn][maxn];
char s2[maxn][maxn];
bool vis[maxb];
 
inline bool Judge(Node a){
    for(res int i=1;i<=4;++i){
        for(res int j=1;j<=4;++j)
            if(a.s[i][j]!=s2[i][j])return 0;
    }
    return 1;
}
 
inline bool Check(Node a,int x,int y){
    if(a.s[x][y]!='1' && x>=1 && x<=4 && y>=1 && y<=4)return 1;
    return 0;
}
 
inline int Hash(Node a){
    int num=0,sum=0;
    for(res int i=1;i<=4;++i){
        for(res int j=1;j<=4;++j){
            num++;
            if(a.s[i][j]=='1')sum+=(1<<num);
        }
    }
    return sum;
}
 
inline void Bfs(){
    std::queue<Node>q;
    q.push(Node(s1,0));vis[Hash(Node(s1,0))]=1;
    while(!q.empty()){
        Node t=q.front();q.pop();
        if(Judge(t)){ans=t.step;break;}
        for(res int i=1;i<=4;++i){
            for(res int j=1;j<=4;++j){
                if(t.s[i][j]=='1'){
                    for(res int k=0,x,y;k<4;++k){
                        Node b=t;x=i+dx[k],y=j+dy[k];
                        if(Check(t,x,y)){
                            b.s[i][j]='0',b.s[x][y]='1';
                            if(vis[Hash(b)])continue;b.step++;
                            q.push(b),vis[Hash(b)]=1;
                        }
                    }
                }
            }
        }
    }
}
 
int main(){
    for(res int i=1;i<=4;++i)
        scanf("%s",s1[i]+1);
    for(res int i=1;i<=4;++i)
        scanf("%s",s2[i]+1);
    Bfs();
    printf("%d\n",ans);
    return 0;
}