Untitled
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