Giả sử ta có ma trận 2D bậc m x n gọi là chiều cao. Chiều cao [i] [j] đại diện cho chiều cao của ô (i, j). Nếu chúng ta đang ở (0, 0) ô, chúng ta muốn di chuyển đến ô dưới cùng bên phải, (m-1, n-1). Chúng ta có thể di chuyển lên, xuống, sang trái hoặc sang phải, và chúng ta muốn tìm một con đường yêu cầu nỗ lực tối thiểu. Trong bài toán này, nỗ lực của rễ là sự khác biệt tuyệt đối lớn nhất về độ cao giữa hai ô liên tiếp của tuyến đường. Vì vậy, cuối cùng, chúng ta cần tìm ra những nỗ lực tối thiểu cần thiết để đi đến đích.
Vì vậy, nếu đầu vào giống như
| 2 | 3 | 4 |
| 4 | 9 | 5 |
| 6 | 4 | 6 |
thì đầu ra sẽ là 1 vì tuyến đường là [2,3,4,5,6] có hiệu số tuyệt đối lớn nhất là 1 trong các ô liên tiếp.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- r:=số hàng theo chiều cao, c:=số cột theo chiều cao
- queue:=một hàng đợi ban đầu lưu trữ một bộ giá trị (0,0,0)
- trong khi hàng đợi không trống, hãy thực hiện
- cur:=mục đầu tiên của hàng đợi và xóa nó khỏi hàng đợi
- c_eff:=cur [0]
- x:=cur [1]
- y:=cur [2]
- nếu x giống với r-1 và y giống với c-1, thì
- trả về c_eff
- nếu heights [x, y] là một chuỗi trống thì
- chuyển sang lần lặp tiếp theo
- đối với mỗi dx, dy trong [[1,0], [- 1,0], [0,1], [0, -1]], thực hiện
- newx:=x + dx
- newy:=y + dy
- nếu 0 <=newx
- eff:=tối đa là c_eff và | heights [newx, newy] - heights [x, y] |
- chèn tuple (eff, newx, newy) vào hàng đợi
- heights [x, y]:=blank string
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[[2,3,4],[4,9,5],[6,4,6]]
Đầu ra
1