Untitled
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