Leetcode 1368. 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:

img
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.

Example 2:

img
Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

img
Input: grid = [[1,2],[4,3]]
Output: 1

Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

Input: grid = [[4]]
Output: 0

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100

分析

这道题的大意就是给一个m*n的矩阵,里面存在指向4个方向的箭头,顺着箭头走不耗费时间,否则时间+1,求从(0,0)到(m-1,n-1)所需要的最小时间(非最短路径)。

所以这道题的本质意思呢还是在一些规则的限制下,从左上角走到右下角。一开始我看m和n也不是很大,我想DFS/BFS是不是就行了。

思路1 DFS

大致思路就是,从(0,0)开始,每次朝4个方向进行递归,每次递归需要记录走到当前位置花费的cost,同时维护一个visited数组,已经走过的数组不再递归。然后将四个方向的最小值进行返回。为了避免超时,我们再维护一个HashMap,每次取到最小值之后就保存。BFS的话也差不多。

然后,就超时了。。。

思路2 DFS+BFS

TLE之后呢,我就看了lee神的解答。原来这道题的本质就是求矩阵两点最短路径的变体。矩阵中两点距离最短,经典解法就是Dijkstra,正常来讲我们应该先写出Dijkstra的解法,然后优化得到DFS+BFS的解法。但是其实两者的思路是相通的。

Dijkstra的思想是维护一个最短路径表。而对于DFS+BFS来说:

  1. 我们从(0,0)开始,首先根据箭头指示,DFS来将所有cost=0的点都遍历一遍,在表dp[m][n]中记录cost=0的点,并将这些点保存在用来DFS的队列queue中。
  2. 遍历queue,对于每一个cost=0的点都进行其他三个方向的cost+1的遍历,此时将dp中cost=1的点都刷了一遍。
  3. 重复上述步骤,于dp表来讲,我们一步步将cost=0,1,2…的点都填入到表中,从而得到从(0,0)到每个点的最短距离。

代码如下:

class Solution {
    private int[][] dir = new int[][]{{0 ,1}, {0, -1}, {1, 0}, {-1, 0}};

    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int cost = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);

        dfs(grid, dp, 0, 0, 0, queue); // 将cost=0的点更新
        while (!queue.isEmpty()) {
            cost++;
            for (int i = queue.size(); i > 0; i--) {
                int[] top = queue.poll();
                int r = top[0], c = top[1];
                for (int j = 0; j < 4; j++)
                    dfs(grid, dp, r + dir[j][0], c + dir[j][1], cost, queue);
            }
        }
        return dp[m - 1][n - 1];
    }

    private void dfs(int[][] grid, int[][] dp, int r, int c, int cost, Queue<int[]> queue) {
        int m = grid.length, n = grid[0].length;
        if (r < 0 || r >= m || c < 0 || c >= n || dp[r][c] != Integer.MAX_VALUE)
            return;
        queue.offer(new int[]{r, c});
        dp[r][c] = cost;
        int dirIndex = grid[r][c] - 1;
        dfs(grid, dp, r + dir[dirIndex][0], c + dir[dirIndex][1], cost, queue);
    }
}

因为我们总共需要更新m*n个点的值,因此时间复杂度为O(mn),空间复杂度也是O(mn)

参考链接

lee215的解答

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号