2차원 행렬과 row, col, erow0, ecol0, erow1 및 ecol1과 같은 다른 값이 있다고 가정합니다. 현재 위치가 행렬 [row, col]이고 행렬 [erow0, ecol0] 및 행렬 [erow1, ecol1]에 있는 금을 픽업하려는 경우. 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있지만 셀(r, c)에 있을 때 비용 매트릭스 [r, c]를 지불해야 합니다. 해당 셀에 대한 비용을 다시 지불해야 합니다. 우리는 두 위치 모두에서 골드를 획득하기 위한 최소 비용을 찾아야 합니다.
따라서 입력이 다음과 같으면
| 1 | 1 | 1 | 1 | 1 |
| 1 | 10 | 10 | 10 | 10 |
| 1 | 1 | 1 | 10 | 10 |
row =0, col =0, erow0 =0, ecol0 =3, erow1 =2, ecol1 =2이면 출력은 (0, 0)에 있고 위치 (0, 3) 및 (2, 2). 따라서 먼저 (0, 0)에서 (0, 3)으로 3단계 이동한 다음 (0,0)으로 돌아온 다음 1개의 표시된 셀을 따라 (2, 2)로 이동합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
is_valid() 함수를 정의합니다. x, y
가 걸립니다. -
x와 y가 행렬의 범위에 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
-
min_cost() 함수를 정의합니다. 이것은 sx, sy가 걸립니다
-
heap :=항목이 있는 힙 (matrix[sx, sy], sx, sy)
-
dists :=주어진 행렬과 같은 크기의 행렬이고 inf로 채움
-
dist[sx, sy] :=행렬[sx, sy]
-
힙이 비어 있지 않은 동안 수행
-
(cost, x, y) :=힙의 첫 번째 요소 및 힙에서 첫 번째 요소 삭제
-
[(x, y - 1) ,(x + 1, y) ,(x - 1, y) ,(x, y + 1) ]의 각 쌍(nx, ny)에 대해
-
is_valid(nx, ny) 및 matrix[nx, ny] + 비용
-
edge :=행렬[nx, ny]
-
dist[nx, ny] :=에지 + 비용
-
힙에 (에지 + 비용, nx, ny) 삽입
-
-
-
-
반환 거리
-
주요 방법에서 다음을 수행하십시오 -
-
res :=inf
-
a :=min_cost(row, col), b :=min_cost(erow0, ecol0), c :=min_cost(erow1, ecol1)
-
행렬의 행 수까지 범위 0에 있는 i에 대해
-
행렬의 열 개수까지 범위 0의 j에 대해
-
res :=res의 최소값 및 (a[i, j] + b[i, j] + c[i, j] - 2 * matrix[i, j])
-
-
-
반환 해상도
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import heapqimport mathclass 솔루션:def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):def is_valid(x, y):return x>=0 및 y>=0 및 x입력
<미리>[ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10]], 0, 0, 0, 3, 2 , 2
출력
8