Untitled

 avatar
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