You are given a 0-indexed 2D integer array grid
of size m x n
that represents a map of the items in a shop. The integers in the grid represent the following:
0
represents a wall that you cannot pass through.1
represents an empty cell that you can freely move to and from.- All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.
It takes 1
step to travel between adjacent grid cells.
You are also given integer arrays pricing
and start
where pricing = [low, high]
and start = [row, col]
indicates that you start at the position (row, col)
and are interested only in items with a price in the range of [low, high]
(inclusive). You are further given an integer k
.
You are interested in the positions of the k
highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:
- Distance, defined as the length of the shortest path from the
start
(shorter distance has a higher rank). - Price (lower price has a higher rank, but it must be in the price range).
- The row number (smaller row number has a higher rank).
- The column number (smaller column number has a higher rank).
Return the k
highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k
reachable items within the price range, return all of them.
Example 1:

Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3 Output: [[0,1],[1,1],[2,1]] Explanation: You start at (0,0). With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2). The ranks of these items are: - (0,1) with distance 1 - (1,1) with distance 2 - (2,1) with distance 3 - (2,2) with distance 4 Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).
Example 2:

Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2 Output: [[2,1],[1,2]] Explanation: You start at (2,3). With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1). The ranks of these items are: - (2,1) with distance 2, price 2 - (1,2) with distance 2, price 3 - (1,1) with distance 3 - (0,1) with distance 4 Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).
Example 3:

Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3 Output: [[2,1],[2,0]] Explanation: You start at (0,0). With a price range of [2,3], we can take items from (2,0) and (2,1). The ranks of these items are: - (2,1) with distance 5 - (2,0) with distance 6 Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). Note that k = 3 but there are only 2 reachable items within the price range.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= grid[i][j] <= 105
pricing.length == 2
2 <= low <= high <= 105
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n
Solution: BFS + Sorting
Use BFS to collect reachable cells and sort afterwards.
Time complexity: O(mn + KlogK) where K = # of reachable cells.
Space complexity: O(mn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua class Solution { public: vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) { const int m = grid.size(); const int n = grid[0].size(); const vector<int> dirs{1, 0, -1, 0, 1}; vector<vector<int>> seen(m, vector<int>(n)); seen[start[0]][start[1]] = 1; vector<vector<int>> cells; queue<array<int, 3>> q; q.push({start[0], start[1], 0}); while (!q.empty()) { auto [y, x, d] = q.front(); q.pop(); if (grid[y][x] >= pricing[0] && grid[y][x] <= pricing[1]) cells.push_back({d, grid[y][x], y, x}); for (int i = 0; i < 4; ++i) { const int tx = x + dirs[i]; const int ty = y + dirs[i + 1]; if (tx < 0 || tx >= n || ty < 0 || ty >= m || !grid[ty][tx] || seen[ty][tx]++) continue; q.push({ty, tx, d + 1}); } } sort(begin(cells), end(cells), less<vector<int>>()); vector<vector<int>> ans; for (int i = 0; i < min(k, (int)(cells.size())); ++i) ans.push_back({cells[i][2], cells[i][3]}); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment