2577. Minimum Time to Visit a Cell In a Grid

class Solution {
    private static final int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    private record Step(int x, int y, int time){};
    public int minimumTime(int[][] grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1) {
            return -1;
        }

        int m = grid.length;
        int n = grid[0].length;

        Queue<Step> queue = new PriorityQueue<>((a, b) -> a.time - b.time);
        queue.offer(new Step(0,0,0));
        Set<String> visited = new HashSet<>();

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            String key = cur.x + "_" + cur.y;
            if (visited.contains(key)) {
                continue;
            }
            visited.add(key);

            if (cur.x == m - 1 && cur.y == n - 1) {
                return cur.time;
            }

            for (int[] dir : DIRECTIONS) {
                int x = cur.x + dir[0];
                int y = cur.y + dir[1];

                if (x < 0 || x >= m || y < 0 || y >= n) {
                    continue;
                }
                // see Editorial, we can cal next time with an additional wait time
                // so still need visited (no need really to simulate the back and forth re-viist process)
                // odd, waitTime is 0 ex: 1,4 (4- 1= 3) -> 0 1 4 -> 0 1, 2 1, 2 3 -> 4 (4+0)
                // even, waitTime is 1 more, ex: 1, 5, 5-1 = 4 => 01,21,23,43,45,6 (5+1)
                int waitTime = (grid[x][y] - cur.time) % 2 == 0 ? 1 : 0; 
                int nextTime = Math.max(grid[x][y] + waitTime, cur.time+1);
                queue.offer(new Step(x, y, nextTime)); 
            }
        }
        return -1;
    }
}

/**
T: O(mnlogmn)
S: O(mn)

 */