数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：查找在任何单元格中与所有人会面的最小步数
假设我们有一个二维矩阵，其中包含以下值：0 代表空单元格；1 代表墙壁；2 代表一个人。现在，一个人可以在一个时间单位内向上、下、左、右四个方向移动，或者留在原地。我们必须找到一个可行走单元格，使得它最大限度地减少每个人相遇所需的时间，并返回该时间。我们必须记住，两个人可以穿过同一个空单元格，并且您可以假设任何两个人之间总存在某种路径。
因此，如果输入如下所示：
| 2 | 0 | 1 | 0 |
| 1 | 0 | 0 | 2 |
| 2 | 0 | 2 | 0 |
则输出将为 2，因为所有人最多可以在矩阵[1, 1] 位置会面，需要最多 2 步。
为了解决这个问题，我们将遵循以下步骤：
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 bfs()。这将接收 r, c
queue := 定义一个队列，并将一个 (r, c) 对插入其中
dist := 一个键值对映射 {(r, c) : 0}
对于队列中的每个 (r, c) 对，执行以下操作：
如果 dist[r, c] > 15 非零，则
退出循环
对于 (r, c) 的每个邻居 (nr, nc)，执行以下操作：
如果 (nr, nc) 不在 dist 中，则
dist[nr, nc] := dist[r, c] + 1
将 (nr, nc) 插入队列的末尾
返回 dist
从主方法执行以下操作：
dist := null
对于 A 的每个行号 r 和对应的行元素，执行以下操作：
对于每个列号 c 和行[c] 值 val，执行以下操作：
如果 val 等于 2，则
ndist := bfs(r, c)
如果 dist 为 null，则
dist := ndist
否则，
对于 dist 的每个键，执行以下操作：
如果键在 ndist 中，则
dist[key] := dist[key] 和 ndist[key] 的最大值
否则，
移除 dist[key]
如果 dist 不为空，则返回 dist 中所有值的最小值；否则返回 0
示例
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def get_neighbor(r, c):
for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
yield nr, nc
def bfs(r, c):
queue = [(r, c)]
dist = {(r, c): 0}
for r, c in queue:
if dist[r, c] > 15:
break
for nr, nc in get_neighbor(r, c):
if (nr, nc) not in dist:
dist[nr, nc] = dist[r, c] + 1
queue.append((nr, nc))
return dist
dist = None
for r, row in enumerate(A):
for c, val in enumerate(row):
if val == 2:
ndist = bfs(r, c)
if dist is None:
dist = ndist
else:
for key in list(dist.keys()):
if key in ndist:
dist[key] = max(dist[key],ndist[key])
else:
del dist[key]
return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 0, 2],
[2, 0, 2, 0]
]
print(ob.solve(matrix))输入
[ [2, 0, 1, 0], [1, 0, 0, 2], [2, 0, 2, 0] ]
输出
2
浏览量：117
