Untitled
unknown
plain_text
5 months ago
1.6 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(); vector<vector<int>> visit(n, vector<int>(m, 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({0, {0, 0}}); visit[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; if (tx == n - 1 && ty == m - 1) { return curTime; // Đã đến ô cuối cùng } 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) { // Điều kiện đảm bảo di chuyển đúng thời gian int nextTime = max(grid[nx][ny], curTime + 1); if ((nextTime - grid[nx][ny]) % 2 == 1) { nextTime++; } if (nextTime < visit[nx][ny]) { pq.push({nextTime, {nx, ny}}); visit[nx][ny] = nextTime; } } } } return -1; // Không thể đến được ô cuối cùng } };
Editor is loading...
Leave a Comment