UVa_10189_Minesweeper.cpp

Problem Links:

uva10189,

Problem:

Problem B: Minesweeper

The Problem

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, supose 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.

The Input

The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m <= 100) which stands for the number of lines and columns of the field respectively. The next n lines contains exactly m characters and represent the field. Each safe square is represented by an "." character (without the quotes) and each mine square is represented by an "*" character (also without the quotes). The first field line where n = m = 0 represents the end of input and should not be processed.

The Output

For each field, you must print the following message in a line alone:

Field #x:

Where x stands for the number of the field (starting from 1). The next n lines should contain the field with the "." characters replaced by the number of adjacent mines to that square. There must be an empty line between field outputs.

Sample Input

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Sample Output

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

---

© 2001 Universidade do Brasil (UFRJ). Internal Contest Warmup 2001.

Solution:

Simulation.

Source Code:

//Wed Mar  2 00:58:07 CST 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

char check(vector<string> v, int x, int y) {
    int ret = 0;
    int m = v.size();
    int n = v[0].size();

    if (v[x][y] == '*') return v[x][y];

    else {
        if (x > 0 && v[x - 1][y] == '*') ret++;
        if (x > 0 && y > 0 && v[x - 1][y - 1] == '*') ret++;
        if (y > 0 && v[x][y - 1] == '*') ret++;
        if (x + 1 < m && y > 0 && v[x + 1][y - 1] == '*') ret++;
        if (x + 1 < m && v[x + 1][y] == '*') ret++;
        if (x + 1 < m && y + 1 < n && v[x + 1][y + 1] == '*') ret++;
        if (y + 1 < n && v[x][y + 1] == '*') ret++;
        if (x > 0 && y + 1 < n && v[x - 1][y + 1] == '*') ret++;
    }
    return '0' + ret;
}

int main(int argc, char* argv[]) {
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    int m, n;
    int counter = 0;
    while (cin >> m >> n && (m + n)) {
        if (++counter > 1) cout << endl;
        vector<string> v1(m, string(n, '0'));
        for (int i = 0; i < m; i++) {
            cin >> v1[i];
        }
        cout << "Field #" << counter << ":" << endl;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cout << check(v1, i, j);
            }
            cout << endl;
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}