POJ 2920 - Mine Map

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

概要

\(n \times n\) のグリッド上に \(m\) 個の地雷がある。 中央のマスからスタートしてグリッドを調査し、その結果を答える。

• 到達できたマスには . マークをつける
• 周囲8マスに地雷が存在するとき、そこには # マークをつけてそれ以上は進めない
• 到達できなかったマスは ? マークで表す

制約

• \(1 < n < 300\), \(n\) は奇数

解法

BFS するだけ。

 1 #include <cstdio>
 2 #include <string>
 3 #include <vector>
 4 #include <queue>
 5 using namespace std;
 6 
 7 static const int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
 8 static const int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 9 
10 char check(const vector<string>& grid, int r, int c)
11 {
12   const int N = grid.size();
13   for (int d = 0; d < 8; d++) {
14     const int i = r + dr[d], j = c + dc[d];
15     if (0 <= i && i < N && 0 <= j && j < N && grid[i][j] == '*') {
16       return '#';
17     }
18   }
19   return '.';
20 }
21 
22 int main()
23 {
24   int T;
25   scanf("%d", &T);
26   for (int Ti = 1; Ti <= T; Ti++) {
27     int N, M;
28     scanf("%d %d", &N, &M);
29     vector<string> grid(N, string(N, '?'));
30     for (int i = 0; i < M; i++) {
31       int r, c;
32       scanf("%d %d", &r, &c);
33       --r;  --c;
34       grid[r][c] = '*';
35     }
36     queue<pair<int,int> > q;
37     q.push(make_pair(N/2, N/2));
38     while (!q.empty()) {
39       const int r = q.front().first, c = q.front().second;
40       q.pop();
41       grid[r][c] = check(grid, r, c);
42       if (grid[r][c] == '#') {
43         continue;
44       }
45       for (int d = 0; d < 8; d++) {
46         const int i = r + dr[d], j = c + dc[d];
47         if (0 <= i && i < N && 0 <= j && j < N && grid[i][j] == '?') {
48           grid[i][j] = '!';
49           q.push(make_pair(i, j));
50         }
51       }
52     }
53 
54     printf("Scenario #%d:\n", Ti);
55     for (int i = 0; i < N; i++) {
56       puts(grid[i].c_str());
57     }
58     putchar('\n');
59   }
60   return 0;
61 }