解决P2670 NOIP2015 普及组 扫雷游戏

题目描述： 扫雷是一款经典的单人益智游戏。游戏板上有一些方块，每个方块上有一个数字，表示该方块周围八个方块内地雷的数量。玩家需要根据数字来判断哪些方块上有地雷，并标记出来。游戏板上的方块分为两种状态：已翻开和未翻开。已翻开的方块上可以显示数字，未翻开的方块上没有数字，并且可能有地雷。

现在给定一个扫雷游戏板的初始状态，你需要计算并输出扫雷游戏的最终状态。

输入格式： 输入的第一行包含两个整数 n,m，表示游戏板的行数和列数。

接下来 n 行，每行包含 m 个字符。字符只可能是以下三种之一：

• 表示已翻开的方块上有地雷。 . 表示已翻开的方块上没有地雷。 ? 表示未翻开的方块。

输出格式： 输出 n 行，每行包含 m 个字符。字符只可能是以下三种之一：

• 表示已翻开的方块上有地雷。 . 表示已翻开的方块上没有地雷。 ? 表示未翻开的方块。

数据范围： 1 ≤ n,m ≤ 100

示例： 输入： 3 3 ..? .*. ..? 输出： 112 8 112

解决方案： 这道题目可以使用深度优先搜索（DFS）来解决。首先，遍历游戏板的每一个方块，如果方块上有地雷，则将该方块的周围八个方块上的数字加一。然后，再次遍历游戏板的每一个方块，如果方块上没有地雷且周围八个方块上的数字之和为0，则将该方块设置为已翻开状态，并将其周围八个方块递归地设置为已翻开状态。最后，输出最终的游戏板状态。

以下是一个可能的实现方案：

#include #include using namespace std;

int n, m; vector<vector> board;

// 深度优先搜索 void dfs(int x, int y) { // 如果方块已经翻开或超出边界，则返回 if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != '?') { return; }

// 设置方块为已翻开状态
board[x][y] = '.';

// 计算周围八个方块上的数字之和
int sum = 0;
for (int i = -1; i <= 1; i++) {
    for (int j = -1; j <= 1; j++) {
        if (i == 0 && j == 0) {
            continue;
        }
        int nx = x + i;
        int ny = y + j;
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == '*') {
            sum++;
        }
    }
}

// 如果周围八个方块上的数字之和为0，则递归地翻开周围八个方块
if (sum == 0) {
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (i == 0 && j == 0) {
                continue;
            }
            int nx = x + i;
            int ny = y + j;
            dfs(nx, ny);
        }
    }
}

}

int main() { cin >> n >> m; board.resize(n, vector(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> board[i][j]; } }

// 遍历游戏板的每一个方块，如果方块上有地雷，则将其周围八个方块上的数字加一
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (board[i][j] == '*') {
            for (int k = -1; k <= 1; k++) {
                for (int l = -1; l <= 1; l++) {
                    if (k == 0 && l == 0) {
                        continue;
                    }
                    int nx = i + k;
                    int ny = j + l;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] != '*') {
                        board[nx][ny]++;
                    }
                }
            }
        }
    }
}

// 再次遍历游戏板的每一个方块，如果方块上没有地雷且周围八个方块上的数字之和为0，则将其设置为已翻开状态，并递归地翻开周围八个方块
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (board[i][j] == '.' && board[i][j] - '0' == 0) {
            dfs(i, j);
        }
    }
}

// 输出最终的游戏板状态
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cout << board[i][j];
    }
    cout << endl;
}

return 0;

}

复杂度分析： 该解法的时间复杂度为 O(nm)，其中 n 和 m 分别是游戏板的行数和列数。在最坏情况下，需要遍历游戏板的所有方块一次。空间复杂度为 O(nm)，需要使用一个二维数组来存储游戏板的状态