本文涉及知识点
C++BFS算法
LeetCode 2146. 价格范围内最高排名的 K 样物品
给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：
0 表示无法穿越的一堵墙。
1 表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
从一个格子走到上下左右相邻格子花费 1 步。
同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。
你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：
距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。
价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。
行坐标：较小 行坐标的有更高优先级。
列坐标：较小 列坐标的有更高优先级。
请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标 全部 返回。
示例 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,1) 和 (2,0) 。
注意，k = 3 但给定价格范围内只有 2 件物品。
提示：
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
C++BFS
一，BFS各单格到起点的距离。具体过程不赘述了。
二，将价格合适的商品，放到图元向量中，包括：距离，价格，行号，列号。
三，将图元向量排序。
代码
核心代码
class CGrid {
public:
CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}
vector<vector<pair<int, int>>> NeiBo(std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4)
{
vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);
auto Move = [&](int preR, int preC, int r, int c)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (funVilidCur(preR, preC) && funVilidNext(r, c))
{
vNeiBo[Mask(preR, preC)].emplace_back(r, c);
}
};
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
for (int k = 0; k < iConnect; k++)
{
Move(r, c, r + s_Moves[k][0], c + s_Moves[k][1]);
}
}
}
return vNeiBo;
}
void EnumGrid(std::function<void(int, int)> call)
{
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
call(r, c);
}
}
}
inline int Mask(int r, int c) { return m_c * r + c; }
const int m_r, m_c;
const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};
class CBFSLeve {
public :
static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
vector<int> leves(neiBo.size(), -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
for (const auto& next : neiBo[start[i]]) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]]+1;
start.emplace_back(next);
}
}
return leves;
}
static vector<vector<int>> Leve(CGrid& grid, vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4 ) {
auto neiBo = grid.NeiBo(funVilidCur, funVilidCur, iConnect);
vector<vector<int>> leves(grid.m_r, vector<int>(grid.m_c, -1));
for (const auto& [r,c] : start) {
leves[r][c] = 0;
}
for (int i = 0; i < start.size(); i++) {
const int iMask = grid.Mask(start[i].first, start[i].second);
for (const auto& [r1,c1] : neiBo[iMask]) {
if (-1 != leves[r1][c1]) { continue; }
leves[r1][c1] = leves[start[i].first][start[i].second] + 1;
start.emplace_back(r1,c1);
}
}
return leves;
}
};
class Solution {
public:
vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
CGrid cg(grid.size(), grid[0].size());
auto vilid = [&](const int& r, const int& c) {return grid[r][c] > 0; };
auto leves = CBFSLeve::Leve(cg, { {start[0],start[1]} }, vilid, vilid);
vector<tuple<int, int, int, int>> v;
auto enu = [&](const int& r, const int& c) {
if ((grid[r][c] < pricing[0]) || (grid[r][c] > pricing[1])) { return; }
if (leves[r][c] < 0) { return; }
v.emplace_back(leves[r][c], grid[r][c], r, c);
};
cg.EnumGrid(enu);
sort(v.begin(), v.end());
vector<vector<int>> ret;
for (int i = 0; i < min((int)v.size(), k); i++) {
ret.emplace_back(vector<int>{ get<2>(v[i]), get<3>(v[i]) });
}
return ret;
}
};
单元测试
vector<vector<int>> grid;
vector<int> pricing, start;
int k;
TEST_METHOD(TestMethod1)
{
grid = { {2,0,3} }, pricing = { 2,3 }, start = { 0,0 }, k = 6;
auto res = Solution().highestRankedKItems(grid, pricing, start, k);
AssertV2(vector<vector<int>>{ {0, 0}}, res);
}
TEST_METHOD(TestMethod2)
{
grid = { {2,4,3} }, pricing = { 2,3 }, start = { 0,0 }, k = 6;
auto res = Solution().highestRankedKItems(grid, pricing, start, k);
AssertV2(vector<vector<int>>{ {0, 0}, { 0,2 }}, res);
}
TEST_METHOD(TestMethod13)
{
grid = { {1,2,0,1},{1,3,0,1},{0,2,5,1} }, pricing = { 2,5 }, start = { 0,0 }, k = 3;
auto res = Solution().highestRankedKItems(grid, pricing, start, k);
AssertV2(vector<vector<int>>{ {0, 1}, { 1,1 }, { 2,1 }},res);
}
TEST_METHOD(TestMethod14)
{
grid = { {1,2,0,1},{1,3,3,1},{0,2,5,1} }, pricing = { 2,3 }, start = { 2,3 }, k = 2;
auto res = Solution().highestRankedKItems(grid, pricing, start, k);
AssertV2(vector<vector<int>>{ {2, 1}, { 1,2 }}, res);
}
TEST_METHOD(TestMethod15)
{
grid = { {1,1,1},{0,0,1},{2,3,4} }, pricing = { 2,3 }, start = { 0,0 }, k = 3;
auto res = Solution().highestRankedKItems(grid, pricing, start, k);
AssertV2(vector<vector<int>>{ {2, 1}, { 2,0 }}, res);
}
TEST_METHOD(TestMethod16)
{
grid = { {2,0,3},{2,0,3},{2,0,3} }, pricing = { 2,3 }, start = { 0,0 }, k = 6;
auto res = Solution().highestRankedKItems(grid, pricing, start, k);
AssertV2(vector<vector<int>>{ {0, 0}, { 1,0 }, { 2,0 }}, res);
}
