2012年12月2日

UVa 11974 - Switch The Lights


#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;
}

沒有留言:

張貼留言