程序查找在Python的任何单元中满足所有人所需的最低限度步骤
假设我们有一个二维矩阵，其中存在这些值：0表示一个空单元格。1代表墙。2代表一个人。现在，一个人可以沿上，下，左，右四个方向中的任一方向行走，否则将停留在一个时间单位内。我们必须找到一个可步行的牢房，以使每个人见面并返回时间所需的时间减至最少。我们必须记住，两个人可以走过同一个空单元，并且您可以假设任何两个人之间总有一条路。
所以，如果输入像
那么输出将为2，因为所有位置都可以在位置矩阵[1，1]处满足，且最多需要2步。
示例
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