0이 빈 셀을 나타내고 1이 벽을 나타내는 2차원 이진 행렬이 있다고 가정합니다. 왼쪽 위 셀과 오른쪽 아래 셀 사이에 경로가 없도록 벽이 되어야 하는 최소 셀 수를 찾아야 합니다. 왼쪽 위 셀과 오른쪽 아래 셀에는 벽을 놓을 수 없습니다. 대각선이 아닌 왼쪽, 오른쪽, 위, 아래로만 이동할 수 있습니다.
따라서 입력이 다음과 같으면
| 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 :=행렬의 열 개수
-
방문:=새로운 세트
-
주석 :=새 지도, 낮음 :=새 지도
-
타이머 :=0
-
bridge_pts :=새로운 세트
-
par :=새 지도
-
src :=쌍(0, 0)
-
tgt :=쌍 (R − 1, C − 1)
-
dfs() 함수를 정의합니다. 이것은 v, 부모가 필요합니다.
-
v를 방문한 것으로 표시
-
par[v] :=부모, tin[v] :=타이머, 낮음[v] :=타이머
-
타이머 :=타이머 + 1
-
어린이 :=0
-
v의 이웃에 대해 다음을 수행합니다.
-
to가 부모와 같으면
-
다음 반복으로 이동
-
-
to를 방문하면
-
low[v] :=low[v] 및 tin[to]
의 최소값
-
-
그렇지 않으면
-
dfs(to, v)
-
low[v] :=low[v]와 low[to]의 최소값
-
low[to]>=tin[v]이고 부모가 null이 아니면
-
bridge_pts에 v 추가
-
-
어린이 :=어린이 + 1
-
-
-
부모가 null이고 자식이> 1이면
-
bridge_pts에 v 추가
-
-
bfs() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
-
Q :=단일 요소 루트가 있는 목록이 있는 이중 종료 대기열
-
방문:=새 세트 및 처음에 루트 삽입
-
Q가 비어 있지 않은 동안 수행
-
v :=Q의 마지막 요소, Q에서 마지막 요소 삭제
-
v가 tgt와 같으면
-
참을 반환
-
-
v의 이웃에 있는 각 w에 대해 다음을 수행합니다.
-
w를 방문하지 않으면
-
w를 방문한 것으로 표시
-
Q의 왼쪽에 w 삽입
-
-
-
-
거짓을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
dfs(src, null)
-
tgt가 동등하지 않으면
-
0 반환
-
-
bridge_pts의 각 쌍(i, j)에 대해 수행
-
행렬[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