极客教程在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