#include <stdio.h>
#include <string.h>
#define inmap(a, b) ~(a) && ~(b) && a < 4 && b < 4
const int N = 16, M = 65536;
bool g[N], e[N];
int d[M], q[M], hh, tt;
bool read() {
char ch;
do ch = getchar();
while(ch == ' ' || ch == '\n');
return ch == '1';
}
int h(bool t[]) {
int res = 0;
for (int i = 0; i < 16; i ++ ) res |= t[i] << i;
return res;
}
int t;
int swp(int a, int b) {
int res = 0;
for (int i = 0; i < 16; i ++ )
if (i ^ a && i ^ b)
res |= (t >> i & 1) << i;
else if (i ^ a)
res |= (t >> a & 1) << i;
else
res |= (t >> b & 1) << i;
return res;
}
int bfs(int st, int ed) {
memset(d, 0x3f, sizeof d);
d[st] = 0, q[0] = st;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
while (hh <= tt) {
t = q[hh ++ ];
if (t == ed) return d[t];
for (int i = 0, x = 0, y = 0; i < 16; x = ++ i >> 2, y = i % 4)
for (int j = 0; j < 4; j ++ ) {
int s = swp(i, (x + dx[j] << 2) + y + dy[j]);
if (inmap(x + dx[j], y + dy[j]) && d[s] > d[t] + 1)
q[ ++ tt] = s, d[s] = d[t] + 1;
}
}
}
int main() {
for (int i = 0; i < 16; i ++ ) g[i] = read();
for (int i = 0; i < 16; i ++ ) e[i] = read();
printf("%d",bfs(h(g), h(e)));
return 0;
}
六
看不懂看不懂555555
这只是留给抄代码的人用的hh