Cho ma trận nhị phân: 0 (trống), 1 (tường). Tìm số ô tối thiểu cần biến thành tường để không có đường đi giữa (0,0) và (R-1,C-1). Không được đặt tường ở hai ô góc. Chỉ di chuyển 4 hướng.
Ví dụ ma trận 4x4 cho kết quả 2.
Giải pháp
Sử dụng thuật toán tìm articulation points (điểm chia) trong đồ thị lưới:
- DFS từ (0,0) tính tin[v], low[v] (thời gian khám phá và low-link)
- bridge_pts: tập các điểm chia (articulation points) trên mọi đường đi từ src đến tgt
- Đặt tường lên tất cả bridge_pts, chạy BFS kiểm tra xem src còn đến tgt không
- Nếu vẫn đến được → cần 2 tường, ngược lại → 1 tường
- Nếu tgt không trong par (không liên thông từ đầu) → 0
Ví dụ minh họa
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))
Đầu vào
[[0,0,0,0],[0,1,0,0],[0,1,1,0],[0,0,0,0]]
Đầu ra
2