程序查找在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