该程序计算在Python中划分左上和右下单元格所需的墙数

假设我们有一个二维二进制矩阵，其中0表示空单元格，而1表示墙。我们必须找到需要成为墙的最小单元数，以便在左上角单元和右下角单元之间没有路径。我们不能在左上方的单元格和右下方的单元格上放置墙。我们只能左右移动，不能左右移动。

所以，如果输入像

那么输出将为2

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

• R：=矩阵的行数，C：=矩阵的列数

• 参观了：=一套新的

• 锡：=新映射，低：=新映射

• 计时器：= 0

• bridge_pts：=一个新的集合

• par：=新映射

• src：=一对(0,0)

• tgt：=一对（R − 1，C − 1）

• 定义一个功能dfs()。这需要v，父级

• 将v标记为已访问

• par [v]：=父级，tin [v]：=计时器，low [v]：=计时器

• 计时器：=计时器+ 1

• 儿童：= 0

• 对于v的每个邻居

• dfs(to, v)

• 低[v]：=低[v]和低[to]的最小值

• 如果low [to]> = tin [v]并且父级不为null，则

• 儿童：=儿童+ 1

• 将v添加到bridge_pts

• 低[v]：=低[v]和锡[to]的最小值

• 进行下一次迭代

• 如果to与父母相同，则

• 如果到了，那么

• 除此以外，

• 如果parent为null且子代> 1，则

• 将v添加到bridge_pts

• 定义一个功能bfs()。这将扎根

• Q：=带有单元素根目录的双头队列

• 访问过：=一个新集合，最初插入根

• 当Q不为空时，

• 如果不访问w，则

• 将w标记为已访问

• 在Q的左侧插入w

• 返回True

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

• 如果v与tgt相同，则

• 对于v的邻居中的每个w，

• 返回False

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

• dfs(src, null)

• 如果tgt不等于标准杆，则

• 返回0

• 对于bridge_pts中的每对(i,j)，执行

• 矩阵[i，j]：= 1

• 如果bfs(src)是真的，那么

• 返回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