POJ 2386 - Lake Counting

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

概要

N * M のグリッドが与えられ，各マスは W (水) か .(乾いた土地) である．

繋がっている W の集合を池と定義したとき，池の数を答える．

制約

• 1 <= N, M <= 100

解法

BFS の例題みたいな問題．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M;
 9   cin >> N >> M;
10   vector<string> grid(N);
11   for (int i = 0; i < N; i++) {
12     cin >> grid[i];
13   }
14 
15   int ans = 0;
16   for (int i = 0; i < N; i++) {
17     for (int j = 0; j < M; j++) {
18       if (grid[i][j] == 'W') {
19         queue<pair<int,int> > q;
20         q.push(make_pair(i, j));
21         grid[i][j] = '.';
22         while (!q.empty()) {
23           const pair<int,int> p = q.front();
24           q.pop();
25           for (int d = 0; d < 8; d++) {
26             static const int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};
27             static const int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
28             const int k = p.first + di[d];
29             const int l = p.second + dj[d];
30             if (0 <= k && k < N && 0 <= l && l < M && grid[k][l] == 'W') {
31               grid[k][l] = '.';
32               q.push(make_pair(k, l));
33             }
34           }
35         }
36         ++ans;
37       }
38     }
39   }
40   cout << ans << endl;
41   return 0;
42 }