2013年8月29日

UVa 12135 - Switch Bulbs

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &n, &m);
    int mask[40] = {};
    for (int i = 0; i < m; i++) {
      int k;
      scanf("%d", &k);
      while (k--) {
        int id;
        scanf("%d", &id);
        mask[i] |= (1 << id);
      }
    }
    int dis[1 << 15];
    memset(dis, -1, sizeof(dis));
    dis[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int now = q.front();
      q.pop();
      for (int i = 0; i < m; i++) {
        int next = now ^ mask[i];
        if (dis[next] == -1) {
          dis[next] = dis[now] + 1;
          q.push(next);
        }
      }
    }
    printf("Case %d:\n", C++);
    int ask;
    scanf("%d", &ask);
    while (ask--) {
      char s[99];
      scanf("%s", s);
      int state = 0;
      for (int i = 0; s[i]; i++) {
        state = (state << 1) + s[i] - '0';
      }
      printf("%d\n", dis[state]);
    }
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言