样例

#include<bits/stdc++.h>
#include<queue>
#include<unordered_map>
using namespace std;

queue <string> N;
unordered_map <string, int> M;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int BFS(string start, string end){
    N.push(start);
    M[start] = 0;
    while(N.size()){
        auto t = N.front();
        int far = M[t];
        N.pop();
        if(t == end){
            //cout << t;
            return M[t];
        }
        for(int a = 0; a < 16; a ++){
            int x = a / 4; int y = a % 4;
            for(int b = 0; b < 4; b ++){
                int m = x + dx[b];
                int n = y + dy[b];
                if(m < 0 || m >= 4 || n < 0 || n >= 4) continue;
                if(m >= 0 && m < 4 && n >= 0 && n < 4 && t[m * 4 + n] == '0' && t[a] == '1'){
                    swap(t[a], t[m * 4 + n]);
                    if(!M.count(t)){
                        M[t] = far + 1;
                        N.push(t);
                    }
                    swap(t[a], t[m * 4 + n]);
                }
            }
        }
    }
}

int main(){
    string start, end;
    for(int a = 0; a < 16; a ++){
        char b; cin >> b;
        start += b;
    }
    getchar();
    getchar();
    for(int a = 0; a < 16; a ++){
        char c; cin >> c;
        end += c;
    }
    //cout << start << " " << end;
    cout << BFS(start, end);
}