P2670 [NOIP2015 普及组] 扫雷游戏 - C++ 解题报告及代码详解 - 常规

{"title":"P2670 [NOIP2015 普及组] 扫雷游戏 - C++ 解题报告及代码详解","description":"本篇文章详细解析了NOIP2015普及组扫雷游戏的解题思路，并提供完整的C++代码实现，包含深度优先搜索（DFS）算法的应用，以及复杂度分析。","keywords":"NOIP, 普及组, 扫雷游戏, 深度优先搜索, DFS, C++ 代码, 解题报告","content":"题目描述：\n扫雷是一款经典的单人益智游戏。游戏板上有一些方块，每个方块上有一个数字，表示该方块周围八个方块内地雷的数量。玩家需要根据数字来判断哪些方块上有地雷，并标记出来。游戏板上的方块分为两种状态：已翻开和未翻开。已翻开的方块上可以显示数字，未翻开的方块上没有数字，并且可能有地雷。\n\n现在给定一个扫雷游戏板的初始状态，你需要计算并输出扫雷游戏的最终状态。\n\n输入格式：\n输入的第一行包含两个整数 n,m，表示游戏板的行数和列数。\n\n接下来 n 行，每行包含 m 个字符。字符只可能是以下三种之一：\n\n* 表示已翻开的方块上有地雷。\n. 表示已翻开的方块上没有地雷。\n? 表示未翻开的方块。\n\n输出格式：\n输出 n 行，每行包含 m 个字符。字符只可能是以下三种之一：\n\n* 表示已翻开的方块上有地雷。\n. 表示已翻开的方块上没有地雷。\n? 表示未翻开的方块。\n\n数据范围：\n1 ≤ n,m ≤ 100\n\n示例：\n输入：\n3 3\n..?\n..\n..?\n输出：\n112\n8*\n112\n\n解决方案：\n这道题目可以使用深度优先搜索（DFS）来解决。首先，遍历游戏板的每一个方块，如果方块上有地雷，则将该方块的周围八个方块上的数字加一。然后，再次遍历游戏板的每一个方块，如果方块上没有地雷且周围八个方块上的数字之和为0，则将该方块设置为已翻开状态，并将其周围八个方块递归地设置为已翻开状态。最后，输出最终的游戏板状态。\n\n以下是一个可能的实现方案：\n\n#include \n#include \nusing namespace std;\n\nint n, m;\nvector<vector> board;\n\n// 深度优先搜索\nvoid dfs(int x, int y) {\n // 如果方块已经翻开或超出边界，则返回\n if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != '?') {\n return;\n }\n \n // 设置方块为已翻开状态\n board[x][y] = '.';\n \n // 计算周围八个方块上的数字之和\n int sum = 0;\n for (int i = -1; i <= 1; i++) {\n for (int j = -1; j <= 1; j++) {\n if (i == 0 && j == 0) {\n continue;\n }\n int nx = x + i;\n int ny = y + j;\n if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == '') {\n sum++;\n }\n }\n }\n \n // 如果周围八个方块上的数字之和为0，则递归地翻开周围八个方块\n if (sum == 0) {\n for (int i = -1; i <= 1; i++) {\n for (int j = -1; j <= 1; j++) {\n if (i == 0 && j == 0) {\n continue;\n }\n int nx = x + i;\n int ny = y + j;\n dfs(nx, ny);\n }\n }\n }\n}\n\nint main() {\n cin >> n >> m;\n board.resize(n, vector(m));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n cin >> board[i][j];\n }\n }\n \n // 遍历游戏板的每一个方块，如果方块上有地雷，则将其周围八个方块上的数字加一\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n if (board[i][j] == '') {\n for (int k = -1; k <= 1; k++) {\n for (int l = -1; l <= 1; l++) {\n if (k == 0 && l == 0) {\n continue;\n }\n int nx = i + k;\n int ny = j + l;\n if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] != '*') {\n board[nx][ny]++;\n }\n }\n }\n }\n }\n }\n \n // 再次遍历游戏板的每一个方块，如果方块上没有地雷且周围八个方块上的数字之和为0，则将其设置为已翻开状态，并递归地翻开周围八个方块\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n if (board[i][j] == '.' && board[i][j] - '0' == 0) {\n dfs(i, j);\n }\n }\n }\n \n // 输出最终的游戏板状态\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n cout << board[i][j];\n }\n cout << endl;\n }\n \n return 0;\n}\n\n复杂度分析：\n该解法的时间复杂度为 O(nm)，其中 n 和 m 分别是游戏板的行数和列数。在最坏情况下，需要遍历游戏板的所有方块一次。空间复杂度为 O(nm)，需要使用一个二维数组来存储游戏板的状态。"}