POJ 3363 - Annoying painting tool

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

概要

\(n \times m\) の白黒画像が与えられる。 \(r \times c\) の領域のピクセルを全て反転させる操作ができるとき、全体を 0 のみにするのに必要な最小の手数を答える。 できないときは -1 を答える。

制約

• \(1 \le r \le n \le 100\)
• \(1 \le c \le m \le 100\)

解法

左上から見ていって 1 のピクセルがあったらそこを左上として反転させなければならなく、これが最適な手順。

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 void flip(char& c) { if (c == '0') { c = '1'; } else { c = '0'; } }
 6 
 7 int solve(vector<string>& pic, int R, int C)
 8 {
 9   const int N = pic.size(), M = pic[0].size();
10   int c = 0;
11   for (int i = 0; i+R <= N; i++) {
12     for (int j = 0; j+C <= M; j++) {
13       if (pic[i][j] == '1') {
14         ++c;
15         for (int k = 0; k < R; k++) {
16           for (int l = 0; l < C; l++) {
17             flip(pic[i+k][j+l]);
18           }
19         }
20       }
21     }
22   }
23   for (int i = 0; i < N; i++) {
24     for (int j = 0; j < M; j++) {
25       if (pic[i][j] == '1') {
26         return -1;
27       }
28     }
29   }
30   return c;
31 }
32 
33 int main()
34 {
35   int N, M, R, C;
36   while (cin >> N >> M >> R >> C && N != 0) {
37     vector<string> pic(N);
38     for (int i = 0; i < N; i++) {
39       cin >> pic[i];
40     }
41     cout << solve(pic, R, C) << endl;
42   }
43   return 0;
44 }