该程序计算在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