Minesweeper
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
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.
Sample Input
28 8F10122101101FF21121234F1F2F11F21121111211100012FF21101F212F101118 8F10122101101FF21121234F1F2FF1F21121111211100012FF21101F212F10111
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 #include5 #include 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 69 #include 70 #include 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