//UVa 11974 - Switch The Lights #include <stdio.h> #include <vector> using namespace std; int swtch[100]; int main() { int cases; scanf("%d", &cases); for (int cas = 1; cas <= cases; cas++) { int n, m; scanf("%d %d", &n, &m); int nxt = 0, now = 1, end = (1 << n) - 1; vector<int> level[2]; bool seen[32768] = { false }; for (int i = 0; i < m; i++) { swtch[i] = 0; for (int j = 0; j < n; j++) { int bit; scanf("%d", &bit); swtch[i] = (swtch[i] << 1) | bit; } level[nxt].push_back(swtch[i]); seen[swtch[i]] = true; } if (m <= 0) { printf("Case %d: 0\n", cas); continue; } int lvl = 1; bool found = seen[end]; while (!seen[end] && !level[nxt].empty()) { lvl++; now = nxt; nxt = nxt ^ 1; level[nxt].clear(); for (int i = 0; i < m; i++) { for (vector<int>::const_iterator I = level[now].begin(); I != level[now].end(); I++) { int generated = (*I) ^ swtch[i]; if (generated == end) { found = true; break; } if (!seen[generated]) { level[nxt].push_back(generated); seen[generated] = true; } } if (found) break; } if (found) break; } if (found) printf("Case %d: %d\n", cas, lvl); else printf("Case %d: IMPOSSIBLE\n", cas); } return 0; }
Friday, April 24, 2015
UVa 11974 - Switch The Lights
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment