在Python中,编写计算机程序以计算将左上角和右下角单元格分区所需的墙数

在Python中,编写计算机程序以计算将左上角和右下角单元格分区所需的墙数

假设我们有一个二维二进制矩阵,其中0代表空的单元格,1代表墙。我们需要找到最少的单元格数量,以便不会有路径连接左上角单元格和右下角单元格。我们不能在左上角和右下角单元格上放置墙。我们只能左右移动、上下移动而不能进行对角线移动。

所以,如果输入如下:

0 0 0 0
0 1 0 0
0 1 1 0
0 0 0 0

那么输出将是2:

0 1 0 0
0 1 0 0
0 1 1 0
0 0 1 0

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

  • R := 矩阵的行数, C := 矩阵的列数

  • visited := 一个新的集合

  • tin := 一个新的map, low := 一个新的map

  • timer := 0

  • bridge_pts := 一个新的集合

  • par := 一个新的map

  • src := 一对(0,0)

  • tgt := 一对(R – 1, C – 1)

  • 定义函数dfs()。它将接受v和parent

  • 标记v为visited

  • par[v] := parent,tin[v] := timer,low[v] := timer

  • timer := timer + 1

  • children := 0

  • 对于v的每一个相邻元素to,执行以下操作

    • 如果to与parent相同,则进行下一次迭代

    • 如果to已被访问,则

      • low[v] := 最小值(low[v], tin[to])
    • 否则,
      • dfs(to, v)

      • low[v] := 最小值(low[v], low[to])

      • 如果low[to] >= tin[v] and parent不为null,则

      • 将v添加到bridge_pts中

      • children := children + 1

  • 如果parent为null且children>1,则

    • 将v添加到bridge_pts中
  • 定义函数bfs()。它将接受root

  • Q := 一个双向队列,其中包含单个元素root的列表

  • visited := 一个新的集合,最初插入root

  • 当Q不为空时,执行以下操作

    • v := Q的最后一个元素,然后从Q中删除最后一个元素

    • 如果v与tgt相同,则

      • 返回True
    • 对于v的每个相邻元素w,执行以下操作
      • 如果w未被访问,则

      • 标记w为visited

      • 在Q的左侧插入w

  • 返回False

  • 从主方法执行以下操作 –

  • dfs(src,null)

  • 如果tgt不在par中,则

    • 返回0
  • 对于bridge_pts中的每个(i, j)对,执行以下操作
    • matrix[i, j] := 1
  • 如果bfs(src)为true,则
    • 返回2
  • 返回1

我们来看以下实现,以便更好的理解 –

例子

from collections import deque
class Solution:
   def solve(self, matrix):
      R = len(matrix)
      C = len(matrix[0])
      def get_neighbors(i, j):
         for ii, jj in ((i + 1, j), (i− 1, j), (i, j + 1), (i, j − 1)):
            if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == 0:
                yield ii, jj
      visited = set()
      tin = {}
      low = {}
      timer = 0
      bridge_pts = set()
      par = {}
      src = (0, 0)
      tgt = (R− 1, C− 1)
      def dfs(v, parent):
         nonlocal timer
         visited.add(v)
         par[v] = parent
         tin[v] = timer
         low[v] = timer
         timer += 1
         children = 0
         for to in get_neighbors(*v):
            if to == parent:
                continue
            if to in visited:
                low[v] = min(low[v], tin[to])
            else:
                dfs(to, v)
                low[v] = min(low[v], low[to])
                if low[to] >= tin[v] and parent is not None:
                    bridge_pts.add(v)
                children += 1
                if parent is None and children > 1:
                    bridge_pts.add(v)
      def bfs(root):
          Q = deque([root])
          visited = set([root])
          while Q:
             v = Q.pop()
             if v == tgt:
                 return True
             for w in get_neighbors(*v):
                 if w not in visited:
                   visited.add(w)
                   Q.appendleft(w)
          return False
      dfs(src, None)
      if tgt not in par:
          return 0
      for i, j in bridge_pts:
          matrix[i][j] = 1
      if bfs(src):
          return 2
      return 1
ob = Solution()
matrix = [
   [0, 0, 0, 0],
   [0, 1, 0, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 0],
]
print(ob.solve(matrix))

输入

[
   [0, 0, 0, 0],
   [0, 1, 0, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 0],
]

输出

2

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程