다음 값이 있는 2D 행렬이 있다고 가정합니다. 0은 빈 셀을 나타냅니다. 1은 벽을 나타냅니다. 2는 사람을 나타냅니다. 이제 사람은 위, 아래, 왼쪽, 오른쪽의 네 방향 중 하나를 걸을 수 있습니다. 그렇지 않으면 한 시간 단위에 머물 수 있습니다. 우리는 모든 사람이 만나고 시간을 반환하는 데 걸리는 시간을 최소화할 수 있는 걸을 수 있는 감방을 찾아야 합니다. 우리는 두 사람이 같은 빈 셀을 통과할 수 있다는 점을 명심해야 하며 두 사람 사이에는 항상 어떤 길이 있다고 가정할 수 있습니다.
따라서 입력이 다음과 같으면
| 2 | 0 | 1 | 0 |
| 1 | 0 | 0 | 2 |
| 2 | 0 | 2 | 0 |
모든 것이 최대 2단계로 위치 행렬[1, 1]에서 만날 수 있으므로 출력은 2가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
bfs() 함수를 정의합니다. r, c
가 걸립니다. -
queue :=큐를 정의하고 그 안에 (r, c) 쌍을 삽입
-
dist :=키 값 쌍이 있는 맵 {(r, c) :0}
-
대기열의 각 쌍(r, c)에 대해 수행
-
dist[r, c]> 15가 0이 아니면
-
루프에서 나오다
-
-
(r, c)의 각 이웃(nr, nc)에 대해 수행
-
(nr, nc)가 dist에 없으면
-
dist[nr, nc] :=dist[r, c] + 1
-
대기열 끝에 (nr, nc) 삽입
-
-
-
반환 거리
-
-
주요 방법에서 다음을 수행하십시오 -
-
dist :=null
-
각 행 번호 r 및 A의 해당 행 요소에 대해 수행
-
각 열 번호 c와 row[c] val 값에 대해
-
val이 2와 같으면
-
ndist :=bfs(r, c)
-
dist가 null이면
-
dist :=ndist
-
-
그렇지 않으면
-
dist 키의 각 키에 대해
-
키가 ndist에 있으면
-
dist[key] :=dist[key]의 최대값, ndist[key]
-
-
그렇지 않으면
-
dist[키]
제거
-
-
-
-
-
-
-
dist가 비어 있지 않으면 dist의 모든 값 중 최소값을 반환하고, 그렇지 않으면 0을 반환합니다.
예
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def get_neighbor(r, c):
for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
yield nr, nc
def bfs(r, c):
queue = [(r, c)]
dist = {(r, c): 0}
for r, c in queue:
if dist[r, c] > 15:
break
for nr, nc in get_neighbor(r, c):
if (nr, nc) not in dist:
dist[nr, nc] = dist[r, c] + 1
queue.append((nr, nc))
return dist
dist = None
for r, row in enumerate(A):
for c, val in enumerate(row):
if val == 2:
ndist = bfs(r, c)
if dist is None:
dist = ndist
else:
for key in list(dist.keys()):
if key in ndist:
dist[key] = max(dist[key],ndist[key])
else:
del dist[key]
return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 0, 2],
[2, 0, 2, 0]
]
print(ob.solve(matrix)) 입력
[ [2, 0, 1, 0], [1, 0, 0, 2], [2, 0, 2, 0] ]
출력
2