(01 BFS) 1368. Minimum Cost to Make at Least One Valid Path in a Grid

T: O(ElogV), E = 4mn, V = mn

S: O(mn)

class Solution {
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1, 0}, {-1, 0}}; // 1,2,3,4

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // small cost first
        pq.offer(new int[]{0, 0 , 0});
        visited[0][0] = true;
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0];
            int curX = cur[1];
            int curY = cur[2];
            
            if (curX == m - 1 && curY == n - 1) {
                return cost;
            }
            
            for (int i = 0; i < 4; i++) {
                int x = curX + DIRS[i][0];
                int y = curY + DIRS[i][1];
                if (!isValid(m, n, x, y) || visited[x][y]) {
                    continue;
                }
                int addOn = (i+1 == grid[curX][curY]) ? 0 : 1; // is change dir?
                pq.offer(new int[]{cost + addOn, x, y});
                visited[x][y] = true;
            }
        }
        return -1;
    }
    private boolean isValid(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

/*
1 => j+1 right
2 => j-1 left
3 => i+1
4 => i-1

The valid path does not have to be the shortest.


You can modify the sign on a cell one time only.


Return the minimum cost to make the grid have at least one valid path.

[
[1,1,3],   -> -> d
[3,2,2],   d. <- <-
[1,1,4]    -> -> u 
]

*/

Latest

T: O(mn)

S: O(mn)

因為其實只會有兩種 cost, 原本的cost 和另一種 cost+1, 所以可以用一個 queue 即可, cost不變的放前面, cost +1 的放後面, 這樣省去用 pq

所以 time complexity 變成 O(mn)

class Solution {
private int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 0-based, 1 -> 0
    
    private record Result(int x, int y, int cost){};

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        Deque<Result> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[m][n];
        queue.offer(new Result(0, 0, 0)); // 

        while (!queue.isEmpty()) {
            Result cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int cost = cur.cost;

            if (visited[x][y]) { 
                continue;
            }
            visited[x][y] = true; 
            if (x == m-1 && y == n-1) {
                return cost;
            }
            for (int[] dir : DIRECTIONS) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (DIRECTIONS[grid[x][y]-1].equals(dir)) {
                    queue.offerFirst(new Result(nx, ny, cost)); // 1,2-1 = 1,1
                } else {
                    queue.offer(new Result(nx, ny, cost+1)); // 1,2-1 = 1,1
                }
            }
        }
        return 0;
    }
}

/*
1 => j+1 right
2 => j-1 left
3 => i+1
4 => i-1

The valid path does not have to be the shortest.


You can modify the sign on a cell one time only.


Return the minimum cost to make the grid have at least one valid path.

[
[1,1,3],   -> -> d
[3,2,2],   d. <- <-
[1,1,4]    -> -> u 
]

*/