Untitled

 avatar
unknown
plain_text
a month ago
2.2 kB
4
Indexable
/**
  1 -- 2 -- 3
  |    |    |
  2 -- 5 -- 7
  |    |    |
  3 -- 5 -- 1


  - queries 2, 5, 6.
  - priority_queue  {-2, {1,0}} {-3, {0,2}} {-5, {1,1}}
  - indexQuery = 1
  - query = T[indexQuery] = 5
  - score = 2
  - scores = {
    2 -> 1

  }

*/  
class Solution {
public:
    vector<int> maxPoints(const vector<vector<int>>& grid, const vector<int>& queries) {
        int m = grid.size();
        int n = grid[0].size();
        int nbQueries = queries.size();
        vector<vector<bool>> visited(m, std::vector<bool>(n, false));

        vector<int> sortedQueries(queries);
        sort(sortedQueries.begin(), sortedQueries.end());
        
        unordered_map<int, int> scores;
        int indexQuery = 0;
        int score = 0;
        priority_queue<pair<int, pair<int,int>>> q;
        q.push({-grid[0][0], {0, 0}});

        while(!q.empty() && indexQuery < nbQueries) {
            auto top = q.top();
            auto cell = top.second;
            q.pop();
            if (visited[cell.first][cell.second]) {
                continue;
            }
            visited[cell.first][cell.second] = true;
            if (-top.first < sortedQueries[indexQuery]) {
                score++;
                for(int i = max(0, cell.first - 1); i < min(m, cell.first + 2); ++i) {
                    if (!visited[i][cell.second]) {
                        q.push({-grid[i][cell.second], {i, cell.second}});
                    }
                }

                for(int j = max(0, cell.second - 1); j < min(n, cell.second + 2); ++j) {
                    if (!visited[cell.first][j]) {
                        q.push({-grid[cell.first][j], {cell.first, j}});
                    }
                }
            } else {
                q.push(top);
                visited[cell.first][cell.second] = false;
                scores[sortedQueries[indexQuery]] = score;
                indexQuery++;
            }
        }

        if (indexQuery < nbQueries) scores[sortedQueries[indexQuery]] = score;

        vector<int> output;
        for (int i: queries) {
            output.push_back(scores[i]);
        }

        return output;
    }
};
Editor is loading...
Leave a Comment