UVA Problem 11974 - Switch The Lights

main.cpp

#include <algorithm>
#include <queue>
#include <vector>

#include <stdio.h>
#include <string.h>

#define MAX_ELEMS 1 << 16

static bool visited[MAX_ELEMS] = {false};

// make_win_state returns an int with the first n bits turned on.
static inline int make_win_state(int n) { return (1 << n) - 1; }

// transform returns the state of the lights after switching the switches defined by s.
static inline int transform(int state, int s) { return state ^ s; }

int solve(bool* visited, int n, const std::vector<int>& switchs) {
  std::queue<std::pair<int, int>> q;
  q.push(std::make_pair(0, 0));

  int win_state = make_win_state(n);

  while (not q.empty()) {
    std::pair<int, int> val = q.front();
    q.pop();
    int state = val.first;
    int step = val.second;

    visited[state] = true;
    if (state == win_state) return step;

    for (const auto& s : switchs) {
      int new_state = transform(state, s);
      if (visited[new_state]) continue;
      q.push(std::make_pair(new_state, step + 1));
    }
  }

  return 0;
}

int main(void) {
  int t;
  if (scanf("%d", &t) != 1) exit(EXIT_FAILURE);

  for (int c = 1; c <= t; c++) {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) exit(EXIT_FAILURE);

    std::vector<int> switchs;
    for (int i = 0; i < m; i++) {
      int s = 0;
      for (int j = 0; j < n; j++) {
        int tmp;
        if (scanf("%d", &tmp) != 1) exit(EXIT_FAILURE);
        if (tmp == 1) s |= 1 << j;
      }
      switchs.push_back(s);
    }

    memset(visited, false, sizeof(bool) * (1 << n));

    printf("Case %d: ", c);
    int k = solve(visited, n, switchs);
    if (k > 0) {
      printf("%d\n", k);
    } else {
      printf("IMPOSSIBLE\n");
    }
  }
}