POJ 1979 - Red and Black

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

概要

\(W \times H\) のグリッドが与えられる。 . のマスは通ることができ、一方 # のマスは通ることができない。 このとき、スタート地点 @ から到達可能なマスの数を答える。

制約

解法

BFS するだけ。

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