前往
大廳
主題

[leetcode]675. Cut Off Trees for Golf Event

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-24 12:00:10 | 巴幣 2 | 人氣 237

題目: 675. Cut Off Trees for Golf Event
難度: Hard
目前下列解法的時間複雜度: O(n**3)


題目說明

給一個 m*n 大小的 >=0 的整數矩陣,
每格 >1 代表樹高;
>=1 代表可以走;
0 代表不能走。
並且沒有兩棵樹一樣高害我以為是 TSP 想一整天。
一開始在 (0,0) 的位置。每次在矩陣上移動時可選擇: 上、下、左、右。
求:從 (0,0) 經由最矮的樹到最高的樹,走過每顆樹的最短步數。


解法: BFS

1. 每次起點1個,終點1個,每步成本相同,求最低成本路徑。故用 BFS 。
2. 像淹水一樣對每個起點、終點淹一遍。
3. 可選擇從低淹到高,或從高淹到低。所以應該會需要一個 heap 來處理起點、終點之間的順序。


source code

創作回應

相關創作

更多創作