資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢最小努力路徑
假設我們有一個m x n階的二維矩陣height。heights[i][j]表示單元格(i, j)的高度。如果我們在(0, 0)單元格，我們想要移動到右下單元格(m-1, n-1)。我們可以向上、下、左或右移動，我們希望找到一條需要最小努力的路線。在這個問題中，路線的努力是路線中兩個連續單元格之間高度的最大絕對差。因此，最終我們需要找到到達目的地的最小努力。
因此，如果輸入如下：
| 2 | 3 | 4 |
| 4 | 9 | 5 |
| 6 | 4 | 6 |
則輸出為1，因為路線[2,3,4,5,6]中連續單元格的最大絕對差為1。
為了解決這個問題，我們將遵循以下步驟：
- r := heights的行數，c:= heights的列數
- 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 in [[1,0],[-1,0],[0,1],[0,-1]]，執行以下操作：
- newx := x+dx
- newy := y+dy
- 如果0 <= newx < r 且 0 <= newy < c 且 heights[newx, newy]不等於空字串，則
- eff := c_eff和|heights[newx,newy] - heights[x,y]|中的最大值
- 將元組(eff, newx, newy)插入佇列
- heights[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
更新於：2021年10月5日
342 次瀏覽
廣告