아래와 같은 값이 거의 없는 2D 행렬이 있다고 가정합니다. -
-
0은 빈 셀을 나타냅니다.
-
1은 벽을 나타냅니다.
-
2는 사람을 나타냅니다.
여기에서 사람은 이 네 가지 방향(위, 아래, 왼쪽, 오른쪽) 중 하나를 걸을 수 있습니다. 우리는 각 사람이 걸어야 하는 총 이동 거리를 최소화하고 최종적으로 거리를 찾을 수 있도록 벽이 아닌 셀을 찾아야 합니다.
따라서 입력이 다음과 같으면
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 | 2 |
가장 좋은 만남 지점이 오른쪽 하단 모서리이므로 출력은 7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
twos :=새 지도, 비용 :=새 지도
-
행렬의 각 인덱스 i와 행 r에 대해 수행
-
r의 각 인덱스 j와 값 v에 대해 수행
-
v가 2와 같으면
-
2s[i, j] :=[i, j, 0]
-
Cost[i, j] :=주어진 행렬과 같은 크기의 2D 행렬을 만들고 무한대로 채웁니다.
-
-
-
-
각 키 값 쌍(k, q)에 대해 2개로
-
본 :=새로운 세트
-
q가 비어 있지 않은 동안 수행
-
(i, j, 비용) :=q에서 첫 번째 요소 삭제
-
(i, j)가 표시되면
-
다음 반복으로 이동
-
-
추가(i, j) 본
-
비용[k, i, j] :=비용
-
((1, 0), (−1, 0), (0, 1), (0, −1))의 각 (di, dj)에 대해 수행
-
(ni, nj) :=(i + di, j + dj)
-
ni와 nj가 행렬의 범위에 있고 matrix[ni, nj]가 1이 아닌 경우
-
q의 끝에 (ni, nj, 비용 + 1) 삽입
-
-
-
-
-
ans :=무한대
-
행렬의 행 수까지 범위 0에 있는 i에 대해
-
행렬의 열 개수까지 범위 0의 j에 대해
-
cur_cost :=0
-
모든 비용 값 목록의 각 arr에 대해 다음을 수행하십시오.
-
cur_cost :=cur_cost + arr[i, j]
-
-
ans :=ans 및 cur_cost의 최소값
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class 솔루션:def solve(self, matrix):twos ={} 비용 ={} for i, r in enumerate(matrix):for j, v in enumerate(r):if v ==2:twos[ (i, j)] =[(i, j, 0)] 비용[(i, j)] =[[1e9 for _ in matrix[0]] for _in matrix] for k, q in twos.items() :본 =set() while q:i, j, 비용 =q.pop(0) if (i, j) in see:계속 see.add((i, j)) 비용[k][i][j ] =((1, 0), (-1, 0), (0, 1), (0, -1))에서 di, dj에 대한 비용:ni, nj =i + di, j + dj if (ni>=0 및 nj>=0 및 ni 입력
행렬 =[[2, 0, 1, 0],[1, 0, 1, 2],[0, 0, 2, 2]]
출력
7