# minesweeper uva 10189 solution

*minesweeper uva 10189 solution*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System which name we can't really remember. Well, the goal of the game is to find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines there are adjacent to that square. For instance, suppose the following 4x4 field with 2 mines (which are represented by an `*' character): *... .... .*.. .... If we would represent the same field placing the hint numbers described above, we would end up with: *100 2210 1*10 1110 As you may have already noticed, each square may have at most 8 adjacent squares |

*Technique to solve this problem*

As you may have already noticed, each square may have at most 8 adjacent squares. Let us suppose a mine is at (i,j) location. its all adjacent blocs would be

To check all 8 adjacent blocks we will use two helper arrays int dirx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 } and int diry[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }.

- Find each mine and increments count of all valid adjacent squares blocks.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> using namespace std; #define N 101 #define M 101 char mines[N][M]; int omines[N][M]; int dirx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int diry[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; void solve(int u, int v, int n, int m) { for (int i = 0; i < 8; i++) { int x = u + dirx[i]; int y = v + diry[i]; if (x < 0 || y < 0 || x >= n || y >= m) continue; if (mines[x][y] == '.') { omines[x][y]++; } } } int main() { int n = 0; int m = 0; freopen("in.txt", "r", stdin); int t = 0; int Flag = 0; while (scanf("%d%d", &n, &m)) { if (n == 0 && m == 0) { break; } t++; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mines[i][j]; omines[i][j] = 0; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mines[i][j] == '*') { omines[i][j] = '*'; solve(i, j, n, m); } } } // output if (Flag == 1) cout << "\n"; Flag = 1; cout << "Field #" << t << ":" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (omines[i][j] == 42) cout << '*'; else cout << omines[i][j]; } cout << endl; } } return 0; } |

## Leave a Reply