สมมติว่าเรามีเมทริกซ์ 2 มิติของคำสั่ง m x n ที่เรียกว่าความสูง 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 :=จำนวนแถวที่มีความสูง c:=จำนวนคอลัมน์ที่มีความสูง
- queue:=คิวเริ่มเก็บ tuple (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]] ทำ
- newx :=x+dx
- ใหม่ :=y+dy
- ถ้า 0 <=newx
- eff :=สูงสุดของ c_eff และ |heights[newx,newy] - heights[x,y]|
- แทรก tuple (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
