POJ 3279 - Fliptile

http://poj.org/problem?id=3279

概要

M x N のグリッドが与えられ，各マスは 0 か 1 である．

あるマスを踏むと，そのマスおよび上下左右の4マスの値が反転する．

最小のステップ数ですべてのマスを 0 にしたとき，どのマスを踏むべきかを答える． ただし，そのような踏み方が複数存在するときは辞書順で最小のものを答える． また，すべてのマスを 0 にできないときは単に「IMPOSSIBLE」とだけ答える．

制約

解法

一行目の踏み方を決めれば，残りの行の踏み方も一意に定まる．

よって，一行目の踏み方を 2^N 通りすべて試すだけ．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 bool solve(int N, int M, int ans[15][15], const int b[15][15])
 5 {
 6   int m = 1000;
 7   int a[15][15];
 8   for (unsigned s = 0; s < (1<<N); s++) {
 9     for (int j = 0; j < N; j++) {
10       a[0][N-j-1] = (s & (1<<j)) != 0;
11     }
12     static const int di[] = {0, 0, 0, -1};
13     static const int dj[] = {0, -1, 1, 0};
14     int flip = 0;
15     for (int i = 0; i < M-1; i++) {
16       for (int j = 0; j < N; j++) {
17         int c = b[i][j];
18         for (int d = 0; d < 4; d++) {
19           const int k = i + di[d];
20           const int l = j + dj[d];
21           if (0 <= k && k < M && 0 <= l && l < N) {
22             c ^= a[k][l];
23           }
24         }
25         a[i+1][j] = c;
26       }
27     }
28     for (int j = 0; j < N; j++) {
29       int c = b[M-1][j];
30       for (int d = 0; d < 4; d++) {
31         const int k = M-1 + di[d];
32         const int l = j + dj[d];
33         if (0 <= k && k < M && 0 <= l && l < N) {
34           c ^= a[k][l];
35         }
36       }
37       if (c != 0) {
38         goto FAIL;
39       }
40     }
41 
42     for (int i = 0; i < M; i++) {
43       for (int j = 0; j < N; j++) {
44         flip += a[i][j];
45       }
46     }
47     if (flip < m) {
48       m = flip;
49       for (int i = 0; i < M; i++) {
50         for (int j = 0; j < N; j++) {
51           ans[i][j] = a[i][j];
52         }
53       }
54     }
55 FAIL:
56     ;
57   }
58   return m < 1000;
59 }
60 
61 int main()
62 {
63   int M, N;
64   scanf("%d %d", &M, &N);
65   int b[15][15];
66   for (int i = 0; i < M; i++) {
67     for (int j = 0; j < N; j++) {
68       scanf("%d", &b[i][j]);
69     }
70   }
71   int ans[15][15];
72   if (solve(N, M, ans, b)) {
73     for (int i = 0; i < M; i++) {
74       for (int j = 0; j < N; j++) {
75         if (j != 0) {
76           putchar(' ');
77         }
78         printf("%d", ans[i][j]);
79       }
80       putchar('\n');
81     }
82   } else {
83     puts("IMPOSSIBLE");
84   }
85   return 0;
86 }
poj/3279.cc