K Highest Ranked Items Within a Price Range LeetCode solution in C++

1
class Solution {
2
 public:
3
  struct cell {
4
    int dist;
5
    int cost;
6
    int row;
7
    int col;
8
  };
9
  struct compare {
10
    bool operator()(const cell &a, const cell &b) {
11
      if (a.dist != b.dist)
12
        return a.dist < b.dist;
13
      else if (a.cost != b.cost)
14
        return a.cost < b.cost;
15
      else if (a.row != b.row)
16
        return a.row < b.row;
17
      else
18
        return a.col < b.col;
19
    }
20
  };
21

22
  vector<vector<int>> highestRankedKItems(vector<vector<int>> &grid, vector<int> &pricing,
23
                                          vector<int> &start, int k) {
24
    int m = grid.size();
25
    int n = grid[0].size();
26

27
    queue<pair<int, int>> q;
28
    q.push({start[0], start[1]});
29

30
    vector<vector<bool>> vis(m, vector<bool>(n, false));
31
    vis[start[0]][start[1]] = true;
32

33
    int dx[4] = {-1, 0, 1, 0};
34
    int dy[4] = {0, -1, 0, 1};
35
    int dist = 0;
36

37
    priority_queue<cell, vector<cell>, compare> pq;
38
    while (!q.empty()) {
39
      int size = q.size();
40
      while (size--) {
41
        pair<int, int> p = q.front();
42
        q.pop();
43
        if (grid[p.first][p.second] != 1 && grid[p.first][p.second] >= pricing[0] &&
44
            grid[p.first][p.second] <= pricing[1]) {
45
          pq.push({dist, grid[p.first][p.second], p.first, p.second});
46

47
          if (pq.size() > k) pq.pop();
48
        }
49
        for (int k = 0; k < 4; k++) {
50
          int x = p.first + dx[k];
51
          int y = p.second + dy[k];
52

53
          if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && grid[x][y] != 0) {
54
            vis[x][y] = true;
55
            q.push({x, y});
56
          }
57
        }
58
      }
59
      dist++;
60
    }
61

62
    vector<vector<int>> ans;
63
    while (!pq.empty()) {
64
      ans.push_back({pq.top().row, pq.top().col});
65
      pq.pop();
66
    }
67

68
    reverse(ans.begin(), ans.end());
69
    return ans;
70
  }
71
};