POJ 1856 - Sea Battle

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

概要

R * C のグリッドが与えられるので，その中に存在する船の数を答える．

船は必ず長方形の形をしている．

ただし，船同士が辺または点を共有してはならない． もしそのような配置が与えられたときは「Bad placement.」と答える．

制約

解法

グリッドを左上から見ていき，# を見つけたら船の幅と高さを特定し，

をチェックし，ダメなら「Bad placement」，大丈夫ならカウントアップ，と数える．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 char grid[1000][1001];
 6 int R, C;
 7 
 8 int solve()
 9 {
10   int r = 0;
11   for (int i = 0; i < R; i++) {
12     for (int j = 0; j < C; j++) {
13       if (grid[i][j] == '#') {
14         int k = i;
15         while (k < R && grid[k][j] == '#') {
16           ++k;
17         }
18         --k;
19         int l = j;
20         while (l < C && grid[i][l] == '#') {
21           ++l;
22         }
23         --l;
24 
25         const int Y = min(l+1, C-1);
26         for (int y = max(j-1, 0); y <= Y; y++) {
27           if (i > 0 && grid[i-1][y] == '#') {
28             return -1;
29           }
30           if (k < R-1 && grid[k+1][y] == '#') {
31             return -1;
32           }
33         }
34         const int X = min(k+1, R-1);
35         for (int x = max(i-1, 0); x <= X; x++) {
36           if (j > 0 && grid[x][j-1] == '#') {
37             return -1;
38           }
39           if (l < C-1 && grid[x][l+1] == '#') {
40             return -1;
41           }
42         }
43         for (int x = i; x <= k; x++) {
44           for (int y = j; y <= l; y++) {
45             if (grid[x][y] != '#') {
46               return -1;
47             }
48             grid[x][y] = '@';
49           }
50         }
51         ++r;
52       }
53     }
54   }
55   return r;
56 }
57 
58 int main()
59 {
60   while (scanf("%d %d", &R, &C) != EOF && R != 0) {
61     for (int i = 0; i < R; i++) {
62       scanf("%s", grid[i]);
63     }
64     const int r = solve();
65     if (r == -1) {
66       puts("Bad placement.");
67     } else {
68       printf("There are %d ships.\n", r);
69     }
70   }
71   return 0;
72 }
poj/1856.cc