class Solution {
static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
var ans = new ArrayList<List<Integer>>();
int m = grid.length, n = grid[0].length;
var vis = new boolean[m][n];
vis[start[0]][start[1]] = true;
var q = new ArrayList<int[]>();
q.add(start);
while (!q.isEmpty()) { // 分层 BFS
// 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案
q.sort((a, b) -> {
int pa = grid[a[0]][a[1]], pb = grid[b[0]][b[1]];
return pa != pb ? pa - pb : a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
});
for (var p : q)
if (pricing[0] <= grid[p[0]][p[1]] && grid[p[0]][p[1]] <= pricing[1]) {
ans.add(List.of(p[0], p[1]));
if (ans.size() == k) return ans;
}
var tmp = q;
q = new ArrayList<>();
for (var p : tmp)
for (var d : dirs) {
int x = p[0] + d[0], y = p[1] + d[1];
if (0 <= x && x < m && 0 <= y && y < n && !vis[x][y] && grid[x][y] > 0) {
vis[x][y] = true;
q.add(new int[]{x, y});
}
}
}
return ans;
}
}
class Solution:
def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
items = [] # 感兴趣物品的信息
q = deque([(start[0], start[1], 0)]) # 广度优先搜索队列
if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:
items.append([0, grid[start[0]][start[1]], start[0], start[1]])
grid[start[0]][start[1]] = 0 # 避免重复遍历
m = len(grid)
n = len(grid[0])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while q:
x, y, d = q.popleft()
for i in range(4):
# 遍历相邻坐标，并进行对应操作
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
q.append((nx, ny, d + 1))
if pricing[0] <= grid[nx][ny] <= pricing[1]:
items.append([d + 1, grid[nx][ny], nx, ny])
grid[nx][ny] = 0 # 避免重复遍历
items.sort() # 按照优先级从高到低排序
res = [item[2:] for item in items][:k] # 排名最高 k 件物品的坐标
return res
class Solution:
def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
ans = []
m, n = len(grid), len(grid[0])
low, high = pricing
sx, sy = start
vis = {(sx, sy)}
q = [(sx, sy)]
while q: # 分层 BFS
# 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案
q.sort(key=lambda p: (grid[p[0]][p[1]], p))
ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)
if len(ans) >= k: return ans[:k]
tmp = q
q = []
for i, j in tmp:
for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:
vis.add((x, y))
q.append((x, y))
return ans
