用Python检查人可以到达左上角或右下角的单元格的程序，以免发生火灾

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个2D矩阵，其中包含几个不同的值，如下所示-

  • 空单元为0

  • 一个人1

  • 2火

  • 3墙

现在假设只有一个人，并且火势每一个方向都在四个方向（向上，向下，向左和向右）扩展，但是火不能穿过墙壁扩展。我们必须检查该人是否可以移动到左上角或右下角或矩阵。我们必须谨记，在每个回合中，人先移动，然后火势扩大。如果此人与火同时进入任何一个目标牢房，那么他是安全的。因此，如果人走到牢房，然后火以相同的方向向同一牢房扩展，该人仍然可以生存。

所以，如果输入像

000
001
002

那么输出将为True，因为此人可以转到左上角。

为了解决这个问题，我们将遵循以下步骤-

  • R：= A的行数，C：= A的列数

  • 定义一个功能bfs()。这将需要排队

  • dist：=包含键作为队列节点且所有值均为0的映射

  • 当队列不为空时，执行

    • 如果nei不在dist，则

    • dist [nei]：= dist [node] + 1

    • 在队列末尾插入nei

    • node：=队列的左项，然后删除左项

    • 对于节点的每个邻居nei，

    • 返回dist

    • 从主要方法中执行以下操作-

    • fire_que：=双头队列

    • person_que：=双头队列

    • 对于每个行索引r和行A，执行

      • 如果v与1相同，则

      • 否则，当v与2相同时，则

      • 在person_que的末尾插入对(r,c)

      • 在fire_que的末尾插入(r,c)对

      • dist_fire：= bfs(fire_que)

      • 对于行中的每个列索引c和值v，执行

      • dist_person：= bfs(person_que)

      • 对于(0,0)，（R − 1，C − 1）中的每个位置

        • 返回True

        • 如果（dist_fire [place]如果不存在，则INF）> =（dist_person [place]如果不存在，则2 * INF），然后

      • 返回False

      让我们看下面的实现以更好地理解-

      示例

      from collections import deque
      class Solution:
         def solve(self, A):
            INF = int(1e9)
            R, C = len(A), len(A[0])
            def get_nei(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] != 3:
                     yield nr, nc
               def bfs(queue):
                  dist = {node: 0 for node in queue}
                  while queue:
                     node = queue.popleft()
                     for nei in get_nei(*node):
                        if nei not in dist:
                           dist[nei] = dist[node] + 1
                           queue.append(nei)
                  return dist
               fire_que = deque()
               person_que = deque()
               for r, row in enumerate(A):
                  for c, v in enumerate(row):
                     if v == 1:
                        person_que.append((r, c))
                     elif v == 2:
                        fire_que.append((r, c))
               dist_fire = bfs(fire_que)
               dist_person = bfs(person_que)
               for place in ((0, 0), (R− 1, C− 1)):
                  if dist_fire.get(place, INF) >= dist_person.get(place, 2 * INF):
                     return True
               return False
      ob = Solution()
      matrix = [
         [0, 0, 0],
         [0, 0, 1],
         [0, 0, 2]
      ]
      print(ob.solve(matrix))

      输入值

      [ [0, 0, 0], [0, 0, 1], [0, 0, 2] ]
      输出结果
      True

      以上是 用Python检查人可以到达左上角或右下角的单元格的程序，以免发生火灾 的全部内容， 来源链接： utcz.com/z/326362.html

      回到顶部