Giả sử chúng ta có một ma trận nhị phân 2d trong đó 0 đại diện cho ô trống và 1 đại diện cho một bức tường. Chúng ta phải tìm số ô tối thiểu cần phải trở thành bức tường để không có đường đi giữa ô trên cùng bên trái và ô dưới cùng bên phải. Chúng ta không thể đặt các bức tường ở ô trên cùng bên trái và ô dưới cùng bên phải. Chúng ta chỉ có thể di chuyển sang trái, phải, lên và xuống chứ không phải theo đường chéo.
Vì vậy, nếu đầu vào giống như
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
thì đầu ra sẽ là 2,
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
R:=số hàng của ma trận, C:=số cột của ma trận
-
đã ghé thăm:=một tập hợp mới
-
tin:=a new map, low:=a new map
-
bộ đếm thời gian:=0
-
bridge_pts:=một tập hợp mới
-
par:=một bản đồ mới
-
src:=a pair (0, 0)
-
tgt:=một cặp (R - 1, C - 1)
-
Định nghĩa một hàm dfs (). Điều này sẽ lấy v, cha mẹ
-
đánh dấu v là đã ghé thăm
-
par [v]:=parent, tin [v]:=timer, low [v]:=timer
-
timer:=timer + 1
-
trẻ em:=0
-
cho từng người hàng xóm của v, do
-
nếu to giống với cha mẹ thì
-
chuyển sang lần lặp tiếp theo
-
-
nếu đến được truy cập, thì
-
low [v]:=tối thiểu là low [v] và tin [to]
-
-
nếu không,
-
dfs (to, v)
-
low [v]:=tối thiểu là low [v] và low [to]
-
nếu low [to]> =tin [v] và cha không phải là null thì
-
thêm v vào bridge_pts
-
-
trẻ em:=trẻ em + 1
-
-
-
nếu cha mẹ là null và con> 1, thì
-
thêm v vào bridge_pts
-
-
Định nghĩa một hàm bfs (). Điều này sẽ bắt nguồn từ gốc
-
Q:=một hàng đợi kết thúc kép với một danh sách có gốc phần tử duy nhất
-
đã thăm:=một tập hợp mới và ban đầu chèn root
-
trong khi Q không trống, thực hiện
-
v:=phần tử cuối cùng của Q, sau đó xóa phần tử cuối cùng khỏi Q
-
nếu v giống với tgt, thì
-
trả về True
-
-
cho mỗi w trong hàng xóm của v, làm
-
nếu w không được truy cập, thì
-
đánh dấu w là đã ghé thăm
-
chèn w vào bên trái của Q
-
-
-
-
trả về Sai
-
Từ phương thức chính, hãy làm như sau -
-
dfs (src, null)
-
nếu tgt không ngang bằng thì
-
trả về 0
-
-
đối với mỗi cặp (i, j) trong bridge_pts, thực hiện
-
ma trận [i, j]:=1
-
-
nếu bfs (src) là true thì
-
trả lại 2
-
-
trả lại 1
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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