Leetcode Problem:
Summary
- Finding Maximum Points in a Grid Based on Queries
Approach
- This solution uses a priority queue to keep track of the cells in the grid that need to be visited
- The priority queue is implemented using a binary heap
- The solution starts from the top left cell and keeps track of the maximum points that can be obtained for each query
- The time complexity is O(m*n*log(m*n)), where m and n are the dimensions of the grid.
Complexity
- O(m*n*log(m*n))
Explanation
- The solution first initializes a visited matrix to keep track of the cells that have been visited
- It also initializes a priority queue with the top left cell of the grid
- Then, it enters a loop where it pops the cell with the maximum value from the priority queue and marks it as visited
- For each cell, it checks all its adjacent cells and pushes them into the priority queue if they have not been visited before
- Finally, it calculates the maximum points that can be obtained for each query by summing up the points obtained for each cell in the priority queue.
Solution Code:
struct _node{
int r;
int c;
int v;
};
template
struct _heap{
T arr[1000001];
int size;
_heap(){
size = 1;
}
void push(T a){
arr[size++] = a;
int idx = size - 1;
while(idx > 1 && arr[idx/2].v > arr[idx].v){
T t = arr[idx/2];
arr[idx/2] = arr[idx];
arr[idx] = t;
idx /= 2;
}
}
T pop(){
T ret = arr[1];
arr[1] = arr[--size];
int i = 1;
while(true){
int j = i * 2;
if(j >= size) break;
if(j + 1 < size && arr[j].v > arr[j+1].v){
j++;
}
if(arr[i].v > arr[j].v){
T t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i = j;
} else{
break;
}
}
return ret;
}
bool empty(){
return size == 1;
}
};
class Solution {
public:
_heap<_node> h;
bool visited[1001][1001];
int answer[1000001] = {0};
vector maxPoints(vector>& grid, vector& queries) {
vector ans;
int cur_query = 0;
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
visited[0][0] = true;
h.push({0, 0, grid[0][0]});
while(!h.empty()){
_node nod = h.pop();
cur_query = max(cur_query, nod.v);
answer[cur_query]++;
for(int i = 0 ; i < 4; i++){
int nr = nod.r + dy[i];
int nc = nod.c + dx[i];
if(nr < 0 || nr >= grid.size() || nc < 0 || nc >= grid[0].size() || visited[nr][nc]){
continue;
}
visited[nr][nc] = true;
h.push({nr, nc, grid[nr][nc]});
}
}
for(int i = 1 ; i < 1000001; i++){
answer[i] = answer[i-1] + answer[i];
}
for(int i = 0 ; i < queries.size(); i++){
ans.push_back(answer[queries[i]-1]);
}
return ans;
}
};
struct _node{
int r;
int c;
int v;
};
template
struct _heap{
T arr[1000001];
int size;
_heap(){
size = 1;
}
void push(T a){
arr[size++] = a;
int idx = size - 1;
while(idx > 1 && arr[idx/2].v > arr[idx].v){
T t = arr[idx/2];
arr[idx/2] = arr[idx];
arr[idx] = t;
idx /= 2;
}
}
T pop(){
T ret = arr[1];
arr[1] = arr[--size];
int i = 1;
while(true){
int j = i * 2;
if(j >= size) break;
if(j + 1 < size && arr[j].v > arr[j+1].v){
j++;
}
if(arr[i].v > arr[j].v){
T t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i = j;
} else{
break;
}
}
return ret;
}
bool empty(){
return size == 1;
}
};
class Solution {
public:
_heap<_node> h;
bool visited[1001][1001];
int answer[1000001] = {0};
vector maxPoints(vector>& grid, vector& queries) {
vector ans;
int cur_query = 0;
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
visited[0][0] = true;
h.push({0, 0, grid[0][0]});
while(!h.empty()){
_node nod = h.pop();
cur_query = max(cur_query, nod.v);
answer[cur_query]++;
for(int i = 0 ; i < 4; i++){
int nr = nod.r + dy[i];
int nc = nod.c + dx[i];
if(nr < 0 || nr >= grid.size() || nc < 0 || nc >= grid[0].size() || visited[nr][nc]){
continue;
}
visited[nr][nc] = true;
h.push({nr, nc, grid[nr][nc]});
}
}
for(int i = 1 ; i < 1000001; i++){
answer[i] = answer[i-1] + answer[i];
}
for(int i = 0 ; i < queries.size(); i++){
ans.push_back(answer[queries[i]-1]);
}
return ans;
}
};
'알고리즘' 카테고리의 다른 글
| Partition Labels (0) | 2025.03.30 |
|---|---|
| Apply Operations to Maximize Score (0) | 2025.03.29 |
| Minimum Index of a Valid Split (0) | 2025.03.28 |
| Minimum Operations to Make a Uni-Value Grid (0) | 2025.03.27 |
| Check if Grid can be Cut into Sections (0) | 2025.03.25 |
짬뽕얼큰하게
