#include <cstdio> #include <queue> int main() { int T, c = 1; scanf("%d", &T); while (T--) { int n, m, i, j, s[100]; scanf("%d%d", &n, &m); for (i = 0; i < m; i++) { s[i] = 0; for (j = 0; j < n; j++) { int tmp; scanf("%d", &tmp); s[i] = s[i] * 2 + tmp; } } int source = 0, find = 0, visit[65536] = {}; std::queue<int> q; for (j = 0; j < n; j++) source = source * 2 + 1; q.push(source); printf("Case %d: ", c++); while (!q.empty()) { int now = q.front(), dis = visit[now]; if (!now) { printf("%d\n", dis); find = 1; break; } q.pop(); for (i = 0; i < m; i++) { int temp = now, press = s[i], next = now, two = 1; while (temp || press) { int bit = temp & 1, change = press & 1; if (change) { bit = !bit; if (bit) next += two; else next -= two; } temp >>= 1; press >>= 1; two <<= 1; } if (next != source && !visit[next]) { visit[next] = dis + 1; q.push(next); } } } if (!find) puts("IMPOSSIBLE"); } return 0; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2012年12月2日
UVa 11974 - Switch The Lights
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言