主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的大小為 m × n 之二維陣列 grid，其代表著一間店鋪中物品的分布地圖。grid 中的不同整數代表著以下事物：
0 代表著一道你無法通過的牆壁。
1 代表著一個你可以自由通行的格子。
其他正整數代表著該格子中擁有的物品之價格。同時，你也可以在這些格子中來去自如。
在相鄰的格子之間移動需要花費「一步」。
你同時也被給定整數陣列 pricing 和 start，其中 pricing = [low, high] 和 start = [row, col] 代表著你一開始位於 (row, col) 這個位置且只對價格位於 [low, high] 這個範圍（含端點）中的物品感興趣。其後，你又再被給定一整數 k。
你好奇價格位於給定範圍中的前 k 個最高級之物品所在的位置。級別之分級是以下列第一個不同的條件來決定的：
距離，其定義為從 start 到該位置的最短距離之長度（越短距離的有著更高的級別）。
價格（越低價格的有著更高的級別，但是前提是必須位於價格範圍中）。
列號（越小的列號者有著更高的級別）。
行號（越小的行號者有著更高的級別）。
回傳位於價格範圍中的前 k 個最高級之物品，其順序需以它們的級別排序（由高到低）。如果位於價格範圍中少於 k 個可以抵達的物品，則全數回傳即可。
限制：
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 10 ^ 5
1 ≦ m × n ≦ 10 ^ 5
0 ≦ grid[i][j] ≦ 10 ^ 5
pricing.length == 2
2 ≦ low ≦ high ≦ 10 ^ 5
start.length == 2
0 ≦ row ≦ m - 1
0 ≦ col ≦ n - 1
grid[row][col] > 0
1 ≦ k ≦ m × n
範例測資：
範例 1：
輸入： grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
輸出： [[0,1],[1,1],[2,1]]
解釋： 你開始於 (0, 0)。
在範圍為 [2, 5] 下，我們可以拿取位置 (0, 1) 、(1, 1) 、(2, 1) 和 (2, 2) 的物品。
這些物品的級別為以下順序：
- (0,1)，其距離為 1。
- (1,1)，其距離為 2。
- (2,1)，其距離為 3。
- (2,2)，其距離為 4。
因此，位於價格範圍中 3 個最高級的物品為 (0, 1) 、 (1, 1) 和 (2, 1)。
範例 2：
輸入： grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
輸出： [[2,1],[1,2]]
解釋： 你開始於 (2, 3)。
在範圍為 [2, 3] 下，我們可以拿取位置 (0, 1) 、(1, 1) 、(1, 2) 和 (2, 1) 的物品。
這些物品的級別為以下順序：
- (2,1)，其距離為 2、價格為 2。
- (1,2)，其距離為 2、價格為 3。
- (1,1)，其距離為 3。
- (0,1)，其距離為 4。
因此，位於價格範圍中 2 個最高級的物品為 (2, 1) 和 (1, 2)。
範例 3：
輸入： grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
輸出： [[2,1],[2,0]]
解釋： 你開始於 (0, 0)。
在範圍為 [2, 3] 下，我們可以拿取位置 (2, 0) 和 (2, 1) 的物品。
這些物品的級別為以下順序：
- (2,1)，其距離為 5。
- (2,0)，其距離為 6。
因此，位於價格範圍中 2 個最高級的物品為 (2, 0) 和 (2, 1)。
注意到雖然 k = 3，但是在價格範圍中只有 2 個物品可以抵達並拿取。
解題思維：
其實就是把地圖 grid 當作一個迷宮走（如這題），而且我們是從 start = [row, col] 這個位置開始一步一步地擴散到所有我們可以到的物品之位置。將這些位置連同該物品之價格（當然，價格超出範圍的就忽略）以及抵達所需步數（因為我們是用廣度優先搜尋（Breadth First Search，BFS）的精神來走，所以會是最短距離）一起記錄下來。
接著就是根據題意先按照距離小到大排、距離一樣按價格小到大排、價格一樣按列號小到大、最後如果連列號一樣就按照行號小到大去排。排完之後取前 k 個（如果不足 k 個就全取）即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
