1.题目基本信息

1.1.题目描述

给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：

• 0 表示无法穿越的一堵墙。

• 1 表示可以自由通过的一个空格子。

• 所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。

从一个格子走到上下左右相邻格子花费 1 步。

同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。

你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：

1. 距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。

2. 价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。

3. 行坐标：较小 行坐标的有更高优先级。

4. 列坐标：较小 列坐标的有更高优先级。

请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标 全部 返回。

1.2.题目地址

https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/description/

2.解题方法

2.1.解题思路

广度优先搜索

2.2.解题步骤

第一步，构建维护变量。que维护广搜的元素队列；items数组维护合法的格子项，每项的模式为[到start的距离,价格,行号,列号]

第二步，执行广搜。并更新维护变量

第三步，将items进行升序排列，并取前k个构建结果数组进行返回

3.解题代码

python代码

from collections import deque

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        # 思路：广度优先搜索
        m, n = len(grid), len(grid[0])
        # 第一步，构建维护变量。que维护广搜的元素队列；items数组维护合法的格子项，每项的模式为[到start的距离,价格,行号,列号]
        que = deque([start])
        items = []
        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
        dist = 0
        while que:
            dist += 1
            for _ in range(len(que)):
                r, c = que.popleft()
                for dr, dc in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
                        if pricing[0] <= grid[nr][nc] <= pricing[1]:
                            items.append([dist, grid[nr][nc], nr, nc])
                        que.append([nr, nc])
                        grid[nr][nc] = 0
            # 剪枝
            if len(items) >= k:
                break
        # 第三步，将items进行升序排列，并取前k个构建结果数组进行返回
        items.sort()
        return [[item[2], item[3]] for item in items[:k]]

4.执行结果