bzoj1054: [HAOI2008]移动玩具
爆搜
const int N = 65536,dx[24] = {15, 14, 13, 15, 14, 13, 12, 11, 10, 9, 11, 10, 9, 8, 7, 6, 5, 7, 6, 5, 4, 3, 2, 1},dy[24] = {14, 13, 12, 11, 10, 9, 8, 10, 9, 8, 7, 6, 5, 4, 6, 5, 4, 3, 2, 1, 0, 2, 1, 0};int Hash[N], S, T;queue<int> Q;inline void Input() {Rep(i, 4) {Rep(j, 4) S = (S << 1) + getchar() - '0';getchar();}getchar();Rep(i, 4) {Rep(j, 4) T = (T << 1) + getchar() - '0';getchar();}}inline void Solve() {clr(Hash, 127);while(sz(Q)) Q.pop();for(Q.push(S), Hash[S] = 0; sz(Q);) {int now = Q.front();Q.pop();Rep(i, 24) {int x = now & (1 << dx[i]), y = now & (1 << dy[i]);int next = now - x - y;if(x) next += 1 << dy[i];if(y) next += 1 << dx[i];if(Hash[next] > Hash[now] + 1) {Hash[next] = Hash[now] + 1, Q.push(next);if(next == T) {printf("%d\n", Hash[T]);return;}}}}}int main() {#ifndef ONLINE_JUDGESETIO("1054");#endifInput();if(S == T) puts("0");else Solve();return 0;}?