높이라고 하는 m x n 차수의 2D 행렬이 있다고 가정합니다. height[i][j]는 셀(i, j)의 높이를 나타냅니다. 우리가 (0, 0) 셀에 있다면 오른쪽 아래 셀 (m-1, n-1)로 이동하려고 합니다. 위, 아래, 왼쪽 또는 오른쪽으로 이동할 수 있으며 최소한의 노력이 필요한 경로를 찾고 싶습니다. 이 문제에서 루트 노력은 경로의 연속된 두 셀 사이의 최대 절대 높이 차이입니다. 그래서 마지막으로 목적지까지 이동하는 데 필요한 최소한의 노력을 찾아야 합니다.
따라서 입력이 다음과 같으면
| 2 | 3 | 4 |
| 4 | 9 | 5 |
| 6 | 4 | 6 |
경로가 [2,3,4,5,6]이므로 연속된 셀에서 최대 절대 차이가 1이므로 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- r :=높이의 행 수, c:=높이의 열 수
- queue:=처음에 튜플(0,0,0)을 저장하는 큐
- 대기열이 비어 있지 않은 동안 수행
- cur:=대기열의 첫 번째 항목 및 대기열에서 삭제
- c_eff:=cur[0]
- x:=cur[1]
- y:=cur[2]
- x가 r-1과 같고 y가 c-1과 같으면
- c_eff를 반환
- heights[x, y]가 공백 문자열이면
- 다음 반복으로 이동
- 각 dx,dy에 대해 [[1,0],[-1,0],[0,1],[0,-1]], do
- newx :=x+dx
- newy :=y+dy
- 0 <=newx
- eff :=c_eff 및 |heights[newx,newy]의 최대값 - height[x,y]|
- 튜플(eff, newx, newy)을 큐에 삽입
- 높이[x, y]:=빈 문자열
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import heapq def solve(heights): r,c=len(heights),len(heights[0]) queue=[(0,0,0)] while queue: cur=heapq.heappop(queue) c_eff=cur[0] x=cur[1] y=cur[2] if x==r-1 and y==c-1: return c_eff if heights[x][y]=="": continue for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]: newx=x+dx newy=y+dy if 0<=newx<r and 0<=newy<c and heights[newx][newy]!="": eff = max(c_eff, abs(heights[newx][newy] - heights[x][y])) heapq.heappush(queue,(eff, newx, newy)) heights[x][y]="" matrix = [[2,3,4],[4,9,5],[6,4,6]] print(solve(matrix))
입력
[[2,3,4],[4,9,5],[6,4,6]]
출력
1