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_JUDGE
	SETIO("1054");
	#endif
	Input();
	if(S == T) puts("0");
	else Solve();
	return 0;
}