SPOJ 5151 Alice’s Cube

一开始反应的是用状态压缩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");elseprintf("%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;    
}