2146. K Highest Ranked Items Within a Price Range

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:

1. Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
2. Price (lower price has a higher rank, but it must be in the price range).
3. The row number (smaller row number has a higher rank).
4. 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.

class Solution {
public:
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
        if(!grid[start[0]][start[1]]) return {};

        int mip = max(2,pricing[0]), map = pricing[1], n = grid.size(), m = grid[0].size();
        int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};

        vector<vector<int>> res;
        queue<pair<int, int>> q;
        q.push({start[0], start[1]});
        if(mip <= grid[start[0]][start[1]] and grid[start[0]][start[1]] <= map) {
            res.push_back({start[0], start[1]});
        }
        grid[start[0]][start[1]] = 0;

        while(!q.empty() and res.size() < k) {
            int sz = q.size();
            vector<vector<int>> items;
            while(sz--) {
                auto [y, x] = q.front(); q.pop();
                for(int i = 0; i < 4; i++) {
                    int ny = y + dy[i], nx = x + dx[i];
                    if(0 <= nx and nx < m and 0 <= ny and ny < n and grid[ny][nx]) {
                        q.push({ny,nx});
                        if(mip <= grid[ny][nx] and grid[ny][nx] <= map) {
                            items.push_back({grid[ny][nx], ny, nx});
                        }
                        grid[ny][nx] = 0;
                    }
                }
            }
            sort(items.begin(), items.end());
            for(int i = 0; i < items.size() and res.size() < k; i++) {
                res.push_back({items[i][1], items[i][2]});
            }
        }

        return res;
    }
};