[已解决]扫雷

13728383860

题目描述

扫雷游戏是一款十分经典的单击小游戏。
在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。
玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。
游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。

现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。

注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。


输入

测试数据有多组：

第一行用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。

接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符∗表示相应的格子是地雷格，字符?表示相应的格子是非地雷格子。相邻字符之间无分隔符。


输出

每组输出包括n行，每行m个字符，描述了整个雷区。用&#8727;表示地雷格，用周围地雷格数表示非地雷格。相邻字符之间无分隔符。(1<=n<=100, 1<=m<=100)

输入样例1      
3 3
*??
???
?*?
2 3
?*?
*??
输出样例1
*10
221
1*1
2*1
*21

最佳答案

月排行榜 / 总排行榜

歌者文明清理员

2023-6-2 23:36:02

解题思路：

该问题可以使用 DFS 或 BFS 进行求解。

判断一个格子的周围8个格子是否为地雷格的时候，可以定义偏移量数组 dx={-1,-1,-1,0,0,1,1,1} 和 dy={-1,0,1,-1,1,-1,0,1}，通过循环这两个数组，分别向上、下、左、右、左上、左下、右上和右下 8 个方向扩散，统计周围的地雷数量。如果当前格子周围没有地雷，则继续扩散其周围的格子。

对于地雷格，直接输出字符 '*' 即可，对于非地雷格，输出周围地雷格数即可。

Python3 代码如下：

1. dx = [-1, -1, -1, 0, 0, 1, 1, 1]
   
2. dy = [-1, 0, 1, -1, 1, -1, 0, 1]
   
3. 
   
4. def dfs(x, y):
   
5.     cnt = 0
   
6.     for i in range(8):
   
7.         nx = x + dx[i]
   
8.         ny = y + dy[i]
   
9.         if nx < 1 or nx > n or ny < 1 or ny > m:
   
10.             continue
    
11.         if a[nx][ny] == '*':
    
12.             cnt += 1
    
13.     if cnt > 0:
    
14.         a[x][y] = str(cnt)[0]
    
15.     else:
    
16.         a[x][y] = '-'
    
17.         for i in range(8):
    
18.             nx = x + dx[i]
    
19.             ny = y + dy[i]
    
20.             if nx < 1 or nx > n or ny < 1 or ny > m:
    
21.                 continue
    
22.             if a[nx][ny] == '?':
    
23.                 dfs(nx, ny)
    
24. 
    
25. while True:
    
26.     try:
    
27.         n, m = map(int, input().split())
    
28.         a = []
    
29.         for i in range(n):
    
30.             s = input().strip()
    
31.             a.append(list(s))
    
32.         for i in range(n):
    
33.             for j in range(m):
    
34.                 if a[i][j] == '?':
    
35.                     dfs(i, j)
    
36.         for i in range(n):
    
37.             print(''.join(a[i]))
    
38.     except:
    
39.         break

复制代码

跳转到最佳答案楼层

歌者文明清理员

解题思路：

该问题可以使用 DFS 或 BFS 进行求解。

判断一个格子的周围8个格子是否为地雷格的时候，可以定义偏移量数组 dx={-1,-1,-1,0,0,1,1,1} 和 dy={-1,0,1,-1,1,-1,0,1}，通过循环这两个数组，分别向上、下、左、右、左上、左下、右上和右下 8 个方向扩散，统计周围的地雷数量。如果当前格子周围没有地雷，则继续扩散其周围的格子。

对于地雷格，直接输出字符 '*' 即可，对于非地雷格，输出周围地雷格数即可。

Python3 代码如下：

1. dx = [-1, -1, -1, 0, 0, 1, 1, 1]
   
2. dy = [-1, 0, 1, -1, 1, -1, 0, 1]
   
3. 
   
4. def dfs(x, y):
   
5.     cnt = 0
   
6.     for i in range(8):
   
7.         nx = x + dx[i]
   
8.         ny = y + dy[i]
   
9.         if nx < 1 or nx > n or ny < 1 or ny > m:
   
10.             continue
    
11.         if a[nx][ny] == '*':
    
12.             cnt += 1
    
13.     if cnt > 0:
    
14.         a[x][y] = str(cnt)[0]
    
15.     else:
    
16.         a[x][y] = '-'
    
17.         for i in range(8):
    
18.             nx = x + dx[i]
    
19.             ny = y + dy[i]
    
20.             if nx < 1 or nx > n or ny < 1 or ny > m:
    
21.                 continue
    
22.             if a[nx][ny] == '?':
    
23.                 dfs(nx, ny)
    
24. 
    
25. while True:
    
26.     try:
    
27.         n, m = map(int, input().split())
    
28.         a = []
    
29.         for i in range(n):
    
30.             s = input().strip()
    
31.             a.append(list(s))
    
32.         for i in range(n):
    
33.             for j in range(m):
    
34.                 if a[i][j] == '?':
    
35.                     dfs(i, j)
    
36.         for i in range(n):
    
37.             print(''.join(a[i]))
    
38.     except:
    
39.         break

复制代码

isdkz

这个问题可以通过使用二维数组来解决。我们可以遍历这个雷区数组，当我们找到一个非地雷格子时，我们可以再遍历其周围的八个格子，如果找到地雷格，就将这个非地雷格的值加一。

以下是这个问题的一个基本的Python解决方案：

1. dx = [-1, -1, -1, 0, 0, 1, 1, 1]
   
2. dy = [-1, 0, 1, -1, 1, -1, 0, 1]
   
3. 
   
4. def solve(n, m, grid):
   
5.     result = [['0'] * m for _ in range(n)]
   
6.     for i in range(n):
   
7.         for j in range(m):
   
8.             if grid[i][j] == '*':
   
9.                 result[i][j] = '*'
   
10.                 for dir in range(8):
    
11.                     nx, ny = i + dx[dir], j + dy[dir]
    
12.                     if nx >= 0 and nx < n and ny >= 0 and ny < m and result[nx][ny] != '*':
    
13.                         result[nx][ny] = str(int(result[nx][ny]) + 1)
    
14.     return result
    
15. 
    
16. while True:
    
17.     try:
    
18.         n, m = map(int, input().split())
    
19.         grid = [list(input()) for _ in range(n)]
    
20.         result = solve(n, m, grid)
    
21.         for row in result:
    
22.             print(''.join(row))
    
23.     except EOFError:
    
24.         break
    

复制代码

这段代码首先定义了两个方向数组dx和dy，表示从一个格子移动到其周围八个格子的相对位置。然后定义了函数solve来处理输入的雷区数组。

在solve函数中，首先定义了一个全为'0'的二维数组result作为输出结果。然后，遍历雷区数组，当找到一个地雷格时，将result中的对应位置设为'*'，然后遍历其周围的八个格子，如果找到非地雷格，就将其值加一。

主函数部分首先接收输入的行数和列数，然后读入雷区数组，然后调用solve函数处理并输出结果。

注意，这个程序需要在一个能够处理输入的环境下运行，比如命令行。而且，因为它需要连续的输入，所以需要有一个方法来表示输入结束，这里是使用EOFError异常来处理的。