POJ 1111 - Image Perimeters

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

概要

二次元のグリッドが与えられ，その中の X で表現された形の外周の長さを答える．

制約

解法

BFS．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <complex>
 5 using namespace std;
 6 typedef complex<int> P;
 7 
 8 int main()
 9 {
10   int R, C, row, col;
11   while (cin >> R >> C >> row >> col && !(R == 0 && C == 0 && row == 0 && col == 0)) {
12     vector<vector<bool> > grid(R+2, vector<bool>(C+2, false));
13     for (int i = 1; i <= R; i++) {
14       for (int j = 1; j <= C; j++) {
15         char c;
16         cin >> c;
17         if (c == 'X') {
18           grid[i][j] = true;
19         }
20       }
21     }
22 
23     vector<vector<bool> > visited(R+1, vector<bool>(C+1, false));
24     queue<P> q;
25     q.push(P(row, col));
26     int perimeter = 0;
27     while (!q.empty()) {
28       const P p = q.front();  q.pop();
29       const int r = real(p);
30       const int c = imag(p);
31       if (visited[r][c]) {
32         continue;
33       }
34 
35       visited[r][c] = true;
36       static const int dir_r[] = {-1, 0, 0, 1, -1, -1, 1, 1};
37       static const int dir_c[] = {0, -1, 1, 0, -1, 1, -1, 1};
38       for (int i = 0; i < 4; i++) {
39         const int s = r + dir_r[i];
40         const int d = c + dir_c[i];
41         if (!grid[s][d]) {
42           perimeter++;
43         }
44       }
45       for (int i = 0; i < 8; i++) {
46         const int s = r + dir_r[i];
47         const int d = c + dir_c[i];
48         if (grid[s][d] && !visited[s][d]) {
49           q.push(P(s, d));
50         }
51       }
52     }
53     cout << perimeter << endl;
54   }
55   return 0;
56 }
poj/1111.cc