数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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、matrix、result
如果 matrix[i, j] 不是 'O' 或 result[i, j] 不是 -1，则
返回 False
返回 True
定义一个函数 calculate_dist()。这将接收 matrix
result := 创建一个 M x N 阶矩阵并填充 -1
定义一个双端队列 q
对于 i 从 0 到 M，执行
对于 j 从 0 到 N，执行
result[i, j] := -1
如果 matrix[i, j] 与 'G' 相同，则
pos := [i, j, 0]
将 pos 插入到 q 的左侧
result[i, j] := 0
当 q 的大小 > 0 不为零时，执行
curr := 从 q 中删除最后一个元素
x、y、dist := curr[0]、curr[1]、curr[2]
对于 i 从 0 到 3，执行
如果 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]
将 pos 插入到 q 的左侧
对于 i 从 0 到 M，执行
对于 j 从 0 到 N，执行
显示 result[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
114 次查看
