Untitled

 avatar
unknown
plain_text
5 months ago
1.3 kB
3
Indexable
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
class Solution {
public:
    int minimumTime(vector<vector<int>>& grid) {
        int n = grid.size();
		int m = grid[0].size();
		int visit[1000][1000];
		for(int i=0; i<n; i++) 
			for(int j=0; j<m; j++) 
				visit[i][j] = INT_MAX;
        
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};

		priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({grid[0][0], {0, 0}});
	
        while(!pq.empty()) {
            auto curCell = pq.top();
            pq.pop();
            int curTime = curCell.first;
            int tx = curCell.second.first;
            int ty = curCell.second.second;
            for(int k=0; k<4; k++) {
                int nx = tx + dx[k];
                int ny = ty + dy[k];
                if(nx>=0 && nx<n && ny>=0 && ny<m) {
                    if(curTime + 1 >= grid[nx][ny] && curTime + 1 <= visit[nx][ny]) { 
                        pq.push({curTime + 1, {nx, ny}});
                        visit[nx][ny] = curTime + 1;
                    }
                }
            }
        }
        if(visit[n-1][m-1] == INT_MAX) return -1;
        return visit[n-1][m-1];
    }
};
Editor is loading...
Leave a Comment