UVA 10189 - Minesweeper

解題觀念

BFS & DFS

可以參考我的課程簡報：BFS & DFS
關於 BFS 的基本觀念可以參考我的這篇文章：Algorithm - BFS
關於 DFS 的基本觀念可以參考我的這篇文章：Algorithm - DFS

題目敘述

您玩過《踩地雷》嗎？這是一款可愛的小遊戲，遊戲的目標是找到所有 M × N 地圖內的地雷
遊戲在一個正方形中顯示一個數字，告訴您該正方形附近有多少個地雷

例如，假設下面的4×4的地圖內帶有 2 個地雷 ( 以 * 字元表示 )
如果我們根據上述作法，將遊戲提示數字填入，則結果將為：
每個正方形內的數字最多為 8 ( 因為最多有8個正方形相鄰 )

// 地雷
* . . .
. . . .
. * . .
. . . .

// 數字帶入周遭有多少地雷
*	1	0	0
2	2	1	0
1	*	1	0
1	1	1	0

Input

輸入將包含多組測資
每組測資第一行包含兩個整數 n 和 m ( 0 < n, m ≤ 100 )，代表地圖大小
如果 n = m = 0 代表輸入結束
接下來的n行，每行m個字元，代表整張地圖
每個安全方塊用 “.” 字元表示，每個地雷方塊用 * 字元表示

// Sample Input
4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Output

對於每組測資
輸出第一行為 “Field #k:”，k代表測資編號
接下來輸出題示後的遊戲地圖
每筆測資間請用空白行分隔

// Sample Output
Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

Solution Code

#include<bits/stdc++.h>
using namespace std;

int now, n;
char mp[100+5][100+5];
int cnt[100+5][100+5];
int step[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};

struct Edge{
    int re;
    int ce;
}edge[10000+5];

void initial(){
    now = 0, n = 0;
    for(int i = 0; i <= 100; i++){
        memset(cnt[i], 0, sizeof(cnt[i]));
    }
}

void dfs(int rn, int cn){   
    
    if(now == n){
        return;
    }

    for(int i = 0; i < 8; i++){
        int cx = cn + step[i][0];
        int rx = rn + step[i][1];

        if(cx >= 0 && rx >= 0){
            cnt[rx][cx]++;
        }
    }
    now++;
    dfs(edge[now].re, edge[now].ce);
}
int main(){
    int ca = 1;
    int r, c;
    bool flag = false;
    while(cin >> r >> c && r && c){
        
        initial();
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                cin >> mp[i][j];
                if(mp[i][j] == '*'){
                    edge[n].re = i;
                    edge[n].ce = j;
                    n++;
                }
            }
        }
        bfs(edge[0].re, edge[0].ce);

        if(flag){
            cout << endl;
        }
        cout << "Field #" << ca++ << ":" << endl;

        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(mp[i][j] != '*'){
                    cout << cnt[i][j];
                }
                else{
                    cout << '*';
                }
            }
            cout << endl;
        }
        flag = true;

    }
}