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

Given a m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

• 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
• 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
• 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
• 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn't have to be the shortest.

You can modify the sign on a cell with cost = 1. 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.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

思路：本质上是一个dijkstra算法；就是每次从pq里面找cost最小点走，然后我每遇见一个node，那么就把四个方向可能的值加到pq里面，前提是没有visited过的话。然后这里唯一不一样的是：我新形成的四个方向中如果跟我自己的cell代表的方向一样的话，cost不变，否则cost都要加1；这里的实现方法，没有用pq，原因是cost 要么是cost不变，要么是cost+1，不可能有其他的值，所以，cost不变就丢到前面，cost+1那么就丢到后面，所以这里用deque也是可以的，那么Time:O(m*n), Space: O(m*n);

class Solution {
    private class Node {
        public int x;
        public int y;
        public int cost;
        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
    
    public int minCost(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];
        Deque<Node> deque = new ArrayDeque<Node>();
        deque.offer(new Node(0, 0, 0));
        // 1, 2, 3, 4
        int[][] dirs = {{0,1},{0,-1},{1,0}, {-1,0}};
        while(!deque.isEmpty()) {
            Node node = deque.pollFirst();
            if(node.x == n - 1 && node.y == m -1) {
                return node.cost;
            }
            if(visited[node.x][node.y]) {
                continue;
            } else {
                visited[node.x][node.y] = true;
            }
            for(int k = 0; k < 4; k++) {
                int nx = node.x + dirs[k][0];
                int ny = node.y + dirs[k][1];
                if(0 <= nx && nx < n && 0 <= ny && ny < m && !visited[nx][ny]) {
                    if(grid[node.x][node.y] - 1 == k) { // 注意这里是需要-1的，才能与新的方向对应起来；
                        deque.offerFirst(new Node(nx, ny, node.cost));
                    } else {
                        deque.offerLast(new Node(nx, ny, node.cost + 1));
                    }
                }
            }
        }
        return -1;
    }
}