[已解决]扫雷

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 代码如下：

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs(x, y):
    cnt = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 1 or nx > n or ny < 1 or ny > m:
            continue
        if a[nx][ny] == '*':
            cnt += 1
    if cnt > 0:
        a[x][y] = str(cnt)[0]
    else:
        a[x][y] = '-'
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 1 or nx > n or ny < 1 or ny > m:
                continue
            if a[nx][ny] == '?':
                dfs(nx, ny)

while True:
    try:
        n, m = map(int, input().split())
        a = []
        for i in range(n):
            s = input().strip()
            a.append(list(s))
        for i in range(n):
            for j in range(m):
                if a[i][j] == '?':
                    dfs(i, j)
        for i in range(n):
            print(''.join(a[i]))
    except:
        break

跳转到最佳答案楼层

歌者文明清理员

解题思路：

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

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

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

Python3 代码如下：

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs(x, y):
    cnt = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 1 or nx > n or ny < 1 or ny > m:
            continue
        if a[nx][ny] == '*':
            cnt += 1
    if cnt > 0:
        a[x][y] = str(cnt)[0]
    else:
        a[x][y] = '-'
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 1 or nx > n or ny < 1 or ny > m:
                continue
            if a[nx][ny] == '?':
                dfs(nx, ny)

while True:
    try:
        n, m = map(int, input().split())
        a = []
        for i in range(n):
            s = input().strip()
            a.append(list(s))
        for i in range(n):
            for j in range(m):
                if a[i][j] == '?':
                    dfs(i, j)
        for i in range(n):
            print(''.join(a[i]))
    except:
        break

isdkz

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

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

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

def solve(n, m, grid):
    result = [['0'] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '*':
                result[i][j] = '*'
                for dir in range(8):
                    nx, ny = i + dx[dir], j + dy[dir]
                    if nx >= 0 and nx < n and ny >= 0 and ny < m and result[nx][ny] != '*':
                        result[nx][ny] = str(int(result[nx][ny]) + 1)
    return result

while True:
    try:
        n, m = map(int, input().split())
        grid = [list(input()) for _ in range(n)]
        result = solve(n, m, grid)
        for row in result:
            print(''.join(row))
    except EOFError:
        break

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

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

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

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