学步园

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define inf 0x7fffffff

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}
const int xx[4] = {-1, 1, 0, 0}, yy[4] = {0, 0, -1, 1};
int bg, ed;
bool Ans[5][5], vis[65536];

struct data {
    bool a[5][5];
    int step;
} q[65536];

inline int hash(bool x[5][5]) {
    int k = 1, s = 0;
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++) {
            s += k * x[i][j];
            k <<= 1;
        }
    return s;
}

inline void bfs() {
    int t = 0, w = 1;
    vis[bg] = 1;
    while (t < w) {
        for (int i = 1; i <= 4; i++)
            for (int j = 1; j <= 4; j++) {
                if (q[t].a[i][j]) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + xx[k], y = j + yy[k];
                        if (q[t].a[x][y] || x < 1 || y < 1 || x > 4 || y > 4)
                            continue;
                        swap(q[t].a[x][y], q[t].a[i][j]);
                        int h = hash(q[t].a);
                        if (h == ed) {
                            printf("%d", q[t].step + 1);
                            return;
                        }
                        if (!vis[h]) {
                            q[w] = q[t];
                            q[w++].step++;
                            vis[h]=1;
                        }
                        swap(q[t].a[x][y], q[t].a[i][j]);
                    }
                }
            }
        t++;
    }
}

int main() {
    for (int i = 1; i <= 4; i++) {
        char ch[6];
        scanf("%s", ch + 1);
        for (int j = 1; j <= 4; j++)
            q[0].a[i][j] = ch[j] - '0';
    }
    for (int i = 1; i <= 4; i++) {
        char ch[6];
        scanf("%s", ch + 1);
        for (int j = 1; j <= 4; j++)
            Ans[i][j] = ch[j] - '0';
    }
    bg = hash(q[0].a);
    ed = hash(Ans);
    if (bg == ed) {
        puts("0");
        return 0;
    }
    bfs();
    return 0;
}