สมมติว่าเรามีเมทริกซ์ไบนารี 2d โดยที่ 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 :=จำนวนคอลัมน์ของเมทริกซ์
-
เข้าชมแล้ว :=ชุดใหม่
-
tin :=แผนที่ใหม่ ต่ำ :=แผนที่ใหม่
-
ตัวจับเวลา :=0
-
bridge_pts :=ชุดใหม่
-
พาร์ :=แผนที่ใหม่
-
src :=คู่ (0, 0)
-
tgt :=คู่ (R − 1, C − 1)
-
กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา v, parent
-
ทำเครื่องหมาย v ว่าเข้าชมแล้ว
-
par[v] :=parent, tin[v] :=ตัวจับเวลา, ต่ำ[v] :=ตัวจับเวลา
-
ตัวจับเวลา :=ตัวจับเวลา + 1
-
ลูก :=0
-
สำหรับแต่ละเพื่อนบ้านของ v ทำ
-
ถ้า to เหมือนกับ parent แล้ว
-
ไปทำซ้ำต่อไป
-
-
หากมีการเยี่ยมชมแล้ว
-
ต่ำ[v] :=ต่ำสุดของต่ำ[v] และ tin[to]
-
-
มิฉะนั้น
-
dfs(ถึง, v)
-
ต่ำ[v] :=ต่ำสุดของต่ำ[v] และต่ำ[ถึง]
-
ถ้า low[to]>=tin[v] และ parent ไม่ใช่ null แล้ว
-
เพิ่ม v ลงใน bridge_pts
-
-
เด็ก :=เด็ก + 1
-
-
-
ถ้าพาเรนต์เป็นโมฆะและลูก> 1 แล้ว
-
เพิ่ม v ลงใน bridge_pts
-
-
กำหนดฟังก์ชัน bfs() สิ่งนี้จะหยั่งราก
-
Q :=คิวสองสิ้นสุดพร้อมรายการที่มีรูทองค์ประกอบเดียว
-
เยี่ยมชม :=ชุดใหม่และเริ่มต้นการรูท
-
ในขณะที่ Q ไม่ว่างเปล่าให้ทำ
-
v :=องค์ประกอบสุดท้ายของ Q จากนั้นลบองค์ประกอบสุดท้ายออกจาก Q
-
ถ้า v เหมือนกับ tgt แล้ว
-
คืนค่า True
-
-
สำหรับแต่ละ w ในเพื่อนบ้านของ v ทำ
-
ถ้าไม่ได้ไปเยี่ยมแล้ว
-
ทำเครื่องหมายว่าเยี่ยมชมแล้ว
-
แทรก w ที่ด้านซ้ายของ Q
-
-
-
-
คืนค่าเท็จ
-
จากวิธีหลักให้ทำดังต่อไปนี้ -
-
dfs(src, null)
-
ถ้า tgt ไม่เท่ากัน
-
คืนค่า 0
-
-
สำหรับแต่ละคู่ (i, j) ใน bridge_pts ให้ทำ
-
เมทริกซ์[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
