POJ 2612 - Mine Sweeper

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

概要

n * n のマインスイーパを考える．

地雷の位置とどのマスを既に開けたかが与えられる． そのとき，既に開けたマスに対して周囲に何個の地雷があるかを示す数字を表示し，もし地雷を開けてしまっていたら地雷のあるすべてのマスを * で表示する．

制約

• n <= 10

解法

やるだけ．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 class MineSweeper
 6 {
 7   int N;
 8   vector<vector<bool> > mines;
 9   vector<vector<int> > grid;
10   bool lose;
11 
12 public:
13   MineSweeper(const vector<vector<bool> >& m)
14     : N(m.size()), mines(m), grid(N, vector<int>(N, -1)), lose(false)
15   {}
16 
17   void open(int i, int j)
18   {
19     if (i < 0 || N <= i || j < 0 || N <= j || grid[i][j] >= 0) {
20       return;
21     }
22 
23     if (mines[i][j]) {
24       lose = true;
25       return;
26     }
27     int c = 0;
28     for (int d = 0; d < 8; d++) {
29       static const int di[] = {-1, -1, -1, 0, 1, 1, 1, 0};
30       static const int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};
31       const int k = i + di[d];
32       const int l = j + dj[d];
33       if (0 <= k && k < N && 0 <= l && l < N) {
34         if (mines[k][l]) {
35           ++c;
36         }
37       }
38     }
39     grid[i][j] = c;
40   }
41 
42   void print(ostream& os)
43   {
44     for (int i = 0; i < N; i++) {
45       for (int j = 0; j < N; j++) {
46         if (grid[i][j] >= 0) {
47           os << grid[i][j];
48         } else if (lose && mines[i][j]) {
49           os << '*';
50         } else {
51           os << '.';
52         }
53       }
54       os << endl;
55     }
56   }
57 };
58 
59 int main()
60 {
61   int N;
62   cin >> N;
63   vector<vector<bool> > mines(N, vector<bool>(N));
64   for (int i = 0; i < N; i++) {
65     string s;
66     cin >> s;
67     for (int j = 0; j < N; j++) {
68       mines[i][j] = s[j] == '*';
69     }
70   }
71   MineSweeper ms(mines);
72   for (int i = 0; i < N; i++) {
73     string s;
74     cin >> s;
75     for (int j = 0; j < N; j++) {
76       if (s[j] == 'x') {
77         ms.open(i, j);
78       }
79     }
80   }
81   ms.print(cout);
82   return 0;
83 }