#include <bits/stdc++.h>
using namespace std;
const int N = 5;
inline string read(){
    string ans = " ";
    for(int i = 1; i <= 4; i++){
        string s; s.resize(5);
        scanf("%s", &s[1]);
        ans += s;
    }
    return ans;
}
inline string hsh(char c[5][5]){
    string ans = " ";
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= 4; j++)
            ans += c[i][j];
    return ans;
}
inline void unhsh(string s, char c[5][5]){
    int id = 1;
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= 4; j++)
            c[i][j] = s[id], id++;
}
struct state{
    string st;
    int step;
};
void bfs(string st_bg, string st_ed){
    queue<state> q;
    map<string, bool> vis;
    q.push((state){st_bg, 0}), vis[st_bg] = 1;
    while(q.size()){
        string st_now = q.front().st;
        int steps_now = q.front().step;
        if(st_now == st_ed){
            printf("%d", steps_now);
            return;
        }
        char mp[5][5];
        unhsh(st_now, mp);
        for(int i = 1; i <= 4; i++){
            for(int j = 1; j <= 4; j++){
                if(mp[i][j] == '1'){
                    int dx[] = {-1, 0, 1, 0};
                    int dy[] = {0, 1, 0, -1};
                    for(int k = 0; k < 4; k++){
                        int tx = i + dx[k], ty = j + dy[k];
                        if(tx >= 1 && ty >= 1 && tx <= 4 && ty <= 4 && mp[tx][ty] == '0'){
                            swap(mp[tx][ty], mp[i][j]);
                            string st_new = hsh(mp);
                            if(!vis[st_new]){
                                vis[st_new] = 1;
                                q.push((state){st_new, steps_now + 1});
                            }
                            swap(mp[tx][ty], mp[i][j]);
                        }
                    }
                }
            }
        }
    }
}
int main(){
    string a = read();
    string b = read();
    bfs(a, b);
    return 0;
}

AC on #3, 其余 TLE...

听...听说灌水区人多，就来...来了