Minesweeper（暴力，注意特判）

Minesweeper

Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

SubmitStatus Practice UVALive 4335
原题链接：点击打开链接

Description

Minesweeper is a single-player computer game. Theobjective of the game is to clear an abstract minefield withoutdetonating a mine. When the game is started, the player is presentedwith a grid ofn x m blank squares.If the player clicks on a square without a mine, a digit is revealed inthat square, the digit indicating the number of adjacent squares thatcontain mines. Two squares are adjacent if they share an edge or acorner, i. e. a square can have at most 8 adjacent squares. By usinglogic, players can in many instances use this information to deducethat certain other squares are mine-free (or mine-filled), and proceedto click on additional squares to clear them or mark them with flaggraphics to indicate the presence of a mine.

Clark Kent is a Minesweeper addict. And with help from hisKryptonian (a planet far far away from earth) powers he solves them atlightning speed and gives them to you. Your job is to tell him whetherthe solved version is correct or not. A board is correctly solved iffall flagged squares should contain a mine and every square containing a numberX has exactly X adjacent squares flagged.

Input

The first line of input will contain an integer T <= 20 denoting the number of test cases.
Each test case will be formatted as follows:-

The first line will contain two integers separated by a single space denoting 1<=n<=20 and 1 <=m<=20 respectively.
The next n lines will contain mcharacters each. Each character will either be a digit (0 to 8inclusive) or 'F'. The presence of 'F' indicates that Clark has flaggedthe square. The digits indicate the number of mines in the adjacentsquares.

Output

Output one line per case:-

'Well done Clark!' if the board was solved successfully.
'Please sweep the mine again!' otherwise.

Note that quotes are for clarity only.

Sample Input

Sample Output

Well done Clark!
Please sweep the mine again!

这题因为n和m较小，直接暴力即可，但要注意特判所有格都为F的情况，这种情况肯定是玩家出错了。以下提供两个AC CODE

AC CODE #1

  1 //Memory: 0 KB         Time: 8 MS
  2 //Language: C++ 4.1.2         Result: Accepted
  3 
  4 #include <iostream>
  5 #include <cstdio>
  6 using namespace std;
  7 
  8 int n, m;
  9 char map[22][22];
 10 int move[8][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
 11 
 12 bool check(int i, int j)
 13 {
 14     int cnt, ii, jj;
 15     cnt = map[i][j] - '0';
 16     for(int k = 0; k < 8; k++)
 17     {
 18         ii = i + move[k][0];
 19         jj = j + move[k][1];
 20         if(ii > -1 && ii < n && jj > -1 && jj < m)
 21         {
 22             if(map[ii][jj] == 'F')
 23                 cnt--;
 24         }
 25     }
 26     if(!cnt) return 1;
 27     return 0;
 28 }
 29 
 30 int main()
 31 {
 32     int T;
 33     int i, j;
 34     bool ok, flag;
 35     scanf("%d", &T);
 36     while(T--)
 37     {
 38         ok = 1;
 39         flag = 0;
 40         scanf("%d %d", &n, &m);
 41         for(i = 0; i < n; i++)
 42             scanf("%s", map[i]);
 43         for(i = 0; i < n && ok; i++)
 44         {
 45             for(j = 0; j < m && ok; j++)
 46             {
 47                 if(map[i][j] != 'F')
 48                 {
 49                     ok = check(i, j);
 50                     flag = 1;
 51                 }
 52             }
 53         }
 54         if(ok && flag) puts("Well done Clark!");
 55         else puts("Please sweep the mine again!");
 56     }
 57     return 0;
 58 }
 59 
 60 也可以采取另一个方法，将所有为F的点压入队列，然后遍历队列中的元素，对于每一个F点，将邻接的格子的数（如果该格不是F）减1，最后遍历field，不是全部点为F而且所有点要么是F要么是‘0’，就well done
 61 
 62 AC CODE #2
 63 
 64 //
 65 //Memory: 0 KB         Time: 8 MS
 66 //Language: C++ 4.1.2         Result: Accepted
 67 
 68 #include <iostream>
 69 #include <cstdio>
 70 #include <queue>
 71 using namespace std;
 72 
 73 int n, m;
 74 char field[22][22];
 75 typedef struct Map
 76 {
 77     int y, x;
 78     Map(int i, int j){y = i; x = j;}
 79 
 80 }M;
 81 queue<Map> que;
 82 int move[8][2] = {{1,0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
 83 
 84 void Check(M t)
 85 {
 86     int i, j, k;
 87     for(k = 0; k < 8; k++)
 88     {
 89         i = t.y + move[k][0];
 90         j = t.x + move[k][1];
 91         if(i > -1 && j > -1 && i < n && j < m && field[i][j] != 'F')
 92             field[i][j]--;
 93     }
 94 }
 95 
 96 int main()
 97 {
 98     char c;
 99     int T, i, j;
100     bool ok;
101     scanf("%d", &T);
102     while(T--)
103     {
104         ok = 0;
105         scanf("%d %d", &n, &m);
106         for(i = 0; i < n; i++)
107         {
108             scanf("%c", &c); //吃掉换行符
109             for(j = 0; j < m; j++)
110             {
111                 scanf("%c", &field[i][j]);
112                 if(field[i][j] == 'F')
113                 {
114                     M tmp(i, j);
115                     que.push(tmp);
116                 }
117             }
118         }
119         if(que.size() != n * m) //当que.size() == n * m时，全为F
120         {
121             ok = 1;
122             while(!que.empty())
123             {
124                 M tmp = que.front();
125                 Check(tmp);
126                 que.pop();
127             }
128             for(i = 0; i < n && ok; i++)
129                 for(j = 0; j < m; j++)
130                 {
131                     if(field[i][j] != 'F' && field[i][j] != '0')
132                     {
133                         ok = 0;
134                         break;
135                     }
136                 }
137         }
138         else
139         {
140             while(!que.empty())
141                 que.pop();
142         }
143         if(ok) puts("Well done Clark!");
144         else puts("Please sweep the mine again!");
145     }
146     return 0;
147 }