数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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 := 一个新的映射，low := 一个新的映射
timer := 0
bridge_pts := 一个新的集合
par := 一个新的映射
src := 一个(0, 0)对
tgt := 一个(R − 1, C − 1)对
定义一个函数dfs()。它将接收v和parent作为参数。
标记v为已访问
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]且parent不为空，则
将v添加到bridge_pts
children := children + 1
如果parent为空且children > 1，则
将v添加到bridge_pts
定义一个函数bfs()。它将接收root作为参数。
Q := 一个双端队列，包含一个只有一个元素root的列表
visited := 一个新的集合，并最初插入root
当Q不为空时，执行以下操作：
v := Q的最后一个元素，然后从Q中删除最后一个元素
如果v与tgt相同，则
返回True
对于v的每个相邻节点w，执行以下操作：
如果w未被访问，则
标记w为已访问
将w插入到Q的左侧
返回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
浏览量：179
