使用 Python 查找距离银行警卫的最短距离
假设我们有一个矩阵,其中有三个字母"O"、"G"和"W",其中"O"代表开放空间,"G"代表警卫,"W"代表银行的墙壁,我们必须根据它们与一个警卫的最短距离替换矩阵中的所有 O,否则我们就无法穿过任何墙壁。在输出矩阵中,警卫被替换为 0,墙壁被替换为 -1。
因此,如果输入如下
| O | O | O | O | G |
| O | O | O | W | O |
| O | W | O | O | O |
| G | W | W | W | O |
| O | O | O | O | G |
则输出将是
| 3 | 3 | 2 | 1 | 0 |
| 2 | 3 | 3 | -1 | 1 |
| 1 | -1 | 4 | 3 | 2 |
| 0 | -1 | -1 | -1 | 1 |
| 1 | 2 | 2 | 1 | 0 |
为了解决这个问题,我们将遵循以下步骤 −
M := 5
N := 5
dir_row := [-1, 0, 1, 0]
dir_col := [0, 1, 0, -1]
定义一个函数 is_ok() 。这将需要 i, j
如果 (i 在范围 0 和 M 内) 或 (j 在范围 0 和 j N 内),则
返回 False
返回 True
定义一个函数 isSafe() 。这将需要 i、j、矩阵、结果
如果矩阵[i, j]不是"O"或 result[i, j] 不为 -1,则
返回 False
返回 True
定义一个函数 calculate_dist()。这将采用矩阵
result := 制作一个 M x N 阶矩阵并用 -1 填充
定义一个双端队列 q
对于 0 到 M 范围内的 i,执行
对于 0 到 N 范围内的 j,执行
result[i, j] := -1
如果 matrix[i, j] 与 'G' 相同,则
pos := [i, j, 0]
在 q 的左侧插入 pos
result[i, j] := 0
while size of q > 0 非零,则执行
curr := 从 q 中删除最后一个元素
x, y, dist := curr[0], curr[1], curr[2]
对于范围在 0 到 3 内的 i,则执行
如果 is_ok(x + dir_row[i], y + dir_col[i]) 非零且 isSafe(x + dir_row[i], y + dir_col[i], matrix, result) 非零,则
result[x + dir_row[i], y + dir_col[i]] := dist + 1
pos := [x + dir_row[i], y + dir_col[i], dist + 1]
在 q 的左侧插入 pos
对于 0 到 M 范围内的 i,执行
对于 0 到 N 范围内的 j,执行
显示结果[i, j]
转到下一行
示例
让我们看看下面的实现以便更好地理解 −
from collections import deque as queue M = 5 N = 5 dir_row = [-1, 0, 1, 0] dir_col = [0, 1, 0, -1] def is_ok(i, j): if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)): return False return True def isSafe(i, j,matrix, result): if (matrix[i][j] != 'O' or result[i][j] != -1): return False return True def calculate_dist(matrix): result = [[ -1 for i in range(N)]for i in range(M)] q = queue() for i in range(M): for j in range(N): result[i][j] = -1 if (matrix[i][j] == 'G'): pos = [i, j, 0] q.appendleft(pos) result[i][j] = 0 while (len(q) > 0): curr = q.pop() x, y, dist = curr[0], curr[1], curr[2] for i in range(4): if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1 pos = [x + dir_row[i], y + dir_col[i], dist + 1] q.appendleft(pos) for i in range(M): for j in range(N): if result[i][j] > 0: print(result[i][j], end=" ") else: print(result[i][j],end=" ") print() matrix = [['O', 'O', 'O', 'O', 'G'], ['O', 'O', 'O', 'W', 'O'], ['O', 'W', 'O', 'O', 'O'], ['G', 'W', 'W', 'W', 'O'], ['O', 'O', 'O', 'O', 'G']] calculate_dist(matrix)
输入
[['O', 'O', 'O', 'O', 'G'], ['O', 'O', 'O', 'W', 'O'], ['O', 'W', 'O', 'O', 'O'], ['G', 'W', 'W', 'W', 'O'], ['O', 'O', 'O', 'O', 'G']]
输出
3 3 2 1 0 2 3 3 -1 1 1 -1 4 3 2 0 -1 -1 -1 1 1 2 2 1 0
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

