1368. Minimum Cost to Make at Least One Valid Path in a Grid

 一刷 07/2022

Version #1 BFS

一开始写了一个bug，就是每次都是走到不能再走了，对最后一个点转换方向，但是这样得到的不一定是最优解

反例就是

右 右 下

左 左 左

上 上 右

其实这道题就是求最短路径，BFS就可以了

一个需要注意的地方是由于cost是increasing的，所以如果一个node已经有了minCost，就停止explore了

Time O(MN)

Space O(MN)

Runtime: 11 ms, faster than 98.43% of Java online submissions for Minimum Cost to Make at Least One Valid Path in a Grid.

Memory Usage: 42.3 MB, less than 97.45% of Java online submissions for Minimum Cost to Make at Least One Valid Path in a Grid.

class Solution {

    private int[] dx = new int[]{0, 1, -1, 0, 0};

    private int[] dy = new int[]{0, 0, 0, 1, -1};

    public int minCost(int[][] grid) {

        Integer[][] minCost = new Integer[grid.length][grid[0].length];

        Queue<int[]> que = new ArrayDeque<>();

        addCells(grid, 0, 0, que, minCost, 0);

        while (!que.isEmpty()) {

            int[] curr = que.poll();

            int y = curr[0];

            int x = curr[1];

            if (y == grid.length - 1 && x == grid[0].length - 1) {

                return minCost[y][x];

            }

            for (int i = 1; i <= 4; i++) {

                if (i == grid[y][x]) {

                    continue;

                }

                int ny = y + dy[i];

                int nx = x + dx[i];

                addCells(grid, ny, nx, que, minCost, minCost[y][x] + 1);

            }

        }

        return -1;

    }

    

    private void addCells(int[][] grid, int y, int x, Queue<int[]> que, Integer[][] minCost, int cost) {

        while  (y >= 0 && x >= 0 && y < grid.length && x < grid[0].length && minCost[y][x] == null) {

            // System.out.printf("(%d, %d)=%d\n", y, x, cost);

            que.offer(new int[]{y, x});

            minCost[y][x] = cost;

            int d = grid[y][x];

            y += dy[d];

            x += dx[d];

        }

    }

}