資料結構
網路
關係資料庫管理系統 (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
