一开始反应的是用状态压缩dp来做，后来一看步数很小，只有三步，于是直接暴力就可以了。另外由于测试数据比较多，可以先从最终状态BFS一遍，保留下所有结果，然后每次判断就是O(1)的了。
#include<stdio.h> #include<string.h> #define MAXD 20 #define MAXM 160 #define MAXS 100010 #define INF 0x3f3f3f3f int first[MAXD], e, dis[MAXS], next[MAXM], v[MAXM]; int q[MAXS]; const int ini = (1 << 16) - (1 << 8); void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void addedge() { e = 0; memset(first, -1, sizeof(first)); add(1, 2), add(1, 3), add(1, 5), add(1, 9); add(2, 4), add(2, 6), add(2, 1), add(2, 10); add(3, 1), add(3, 4), add(3, 7), add(3, 11); add(4, 2), add(4, 3), add(4, 8), add(4, 12); add(5, 1), add(5, 6), add(5, 7), add(5, 13); add(6, 2), add(6, 5), add(6, 8), add(6, 14); add(7, 3), add(7, 5), add(7, 8), add(7, 15); add(8, 4), add(8, 7), add(8, 6), add(8, 16); add(9, 1), add(9, 10), add(9, 11), add(9, 13); add(10, 2), add(10, 9), add(10, 12), add(10, 14); add(11, 3), add(11, 9), add(11, 12), add(11, 15); add(12, 4), add(12, 10), add(12, 11), add(12, 16); add(13, 9), add(13, 5), add(13, 14), add(13, 15); add(14, 10), add(14, 13), add(14, 6), add(14, 16); add(15, 7), add(15, 11), add(15, 13), add(15, 16); add(16, 8), add(16, 12), add(16, 14), add(16, 15); } void prepare() { int i, j, k, x, y, rear = 0; addedge(); memset(dis, 0x3f, sizeof(dis)); dis[ini] = 0, q[rear ++] = ini; for(i = 0; i < rear; i ++) { x = q[i]; if(dis[x] >= 3) break; for(j = 1; j <= 16; j ++) for(k = first[j]; k != -1; k = next[k]) { if((x & 1 << j - 1) != (x & 1 << v[k] - 1)) { y = x ^ (1 << j - 1) ^ (1 << v[k] - 1); if(dis[y] == INF) { dis[y] = dis[x] + 1; q[rear ++] = y; } } } } } void solve() { int i, j, k, a[20]; for(i = 0; i < 16; i ++) scanf("%d", &a[i]); k = 0; for(i = 15; i >= 0; i --) k = k << 1 | a[i]; if(dis[k] == INF) printf("more\n"); else printf("%d\n", dis[k]); } int main() { int t, tt; prepare(); scanf("%d", &t); for(tt = 1; tt <= t; tt ++) { printf("Case #%d: ", tt); solve(); } return 0; }