# 2577. Minimum Time to Visit a Cell In a Grid
###### tags: `Leetcode` `Hard` `BFS` `Priority Queue` `Dijkstra`
Link: https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid/description/
## 思路
本质上就是一道dijkstra
记录每个点能到达的最短时间
然后每次在priority queue里面取能最快到的点 然后遍历它的邻居
唯一不同的地方在于如果邻居的minimum time to visit>现在的time+1
说明我们不能直接到那边去 而是要在旁边绕圈 一会再回来
我们可以选择在prev 和curr node中间来回走
curr->prev->...->curr->next
这时候我们会发现如果next和curr差一个偶数 那么我们只能在next+1到达
但是如果中间差一个奇数 那么我们就可以在next到达
## Code

class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if(grid[0][1]>1 && grid[1][0]>1) return -1;
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        pq.add(new int[]{0, 0, 0});
        int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;

        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int time = curr[0], row = curr[1], col = curr[2];
            if(row==m-1 && col==n-1) return time;
            for(int[] dir:dirs){
                int nextx = row+dir[0];
                int nexty = col+dir[1];
                if(nextx<0 || nextx>=m || nexty<0 || nexty>=n || visited[nextx][nexty]) continue;
                int nextTime = time + 1;
                if(grid[nextx][nexty]>time+1) nextTime = ((grid[nextx][nexty]-time)%2==0?1:0)+grid[nextx][nexty];
                pq.add(new int[]{nextTime, nextx, nexty});
                visited[nextx][nexty] = true;
            }
        }
        return -1;
    }
}