POJ 1753 Flip Game

問題

4x4のオセロの盤面が与えられる。盤上の石を一つひっくり返すと4近傍の石もひっくり返るとする。すべての石が同じ色になるために必要なひっくり返す動作の最小回数を求めよ。どうひっくり返しても達成できない場合は"Impossible"を出力せよ。

やりかた

同じ石を2回以上ひっくり返す必要はないので16個の石をそれぞれひっくり返すかどうかのパターンを全列挙して調べれば十分間に合う。

以下ソース。

void flip(int &T, int idx){
  T ^= 1 << idx;
  if(idx + 4 < 16) T ^= 1 << (idx + 4);
  if(idx - 4 >= 0) T ^= 1 << (idx - 4);
  if(idx % 4 != 0) T ^= 1 << (idx - 1);
  if(idx % 4 != 3) T ^= 1 << (idx + 1);
}
int main(int argc, char **argv){
  int S = 0;
  for(int i = 0; i < 4; i++){
    string s; cin >> s;
    for(int j = 0; j < 4; j++)
      if(s[j] == 'w') S |= (1 << (4 * i + j));
  }
  int ans = INF;
  for(int M = 0; M < 1 << 16; M++){
    int T = S, cnt = 0;
    for(int i = 0; i < 16; i++){
      if(!(M >> i & 1)) continue;
      cnt++;
      flip(T, i);
    }
    if(T == 0 || (1 << 16) - 1 == T) ans = min(ans, cnt);
  }
  if(ans == INF) cout << "Impossible" << endl;
  else cout << ans << endl;
  return 0;
}