X

LEETCODE 1368. Minimum Cost to Make at Least One Valid Path in a Grid 解题思路分析

题目大意:

使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字,对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况:

  • 1 ,下一步往右走,也就是你会从 grid[i][j] 走到 grid[i][j + 1]
  • 2 ,下一步往左走,也就是你会从 grid[i][j] 走到 grid[i][j – 1]
  • 3 ,下一步往下走,也就是你会从 grid[i][j] 走到 grid[i + 1][j]
  • 4 ,下一步往上走,也就是你会从 grid[i][j] 走到 grid[i – 1][j]

注意网格图中可能会有 无效数字 ,因为它们可能指向 grid 以外的区域。

一开始,你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发,每一步都顺着数字对应方向走,最终在最右下角的格子 (m – 1, n – 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字,但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

示例 1:

输入:grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出:3
解释:你将从点 (0, 0) 出发。
 到达 (3, 3) 的路径为: (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)
 总花费为 cost = 3.

示例 2:

输入:grid = [[1,1,3],[3,2,2],[1,1,4]]
输出:0
解释:不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

示例 3:

输入:grid = [[1,2],[4,3]]
输出:1

示例 4:

输入:grid = [[2,2,2],[2,2,2]]
输出:3

示例 5:

输入:grid = [[4]]
输出:0

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1368

解题思路分析:


我们之前的文章提到过多次,看到网格(矩阵)类型的题目,首选dfs或者bfs来解题,而本题是求最小cost问题,虽然不是求最小路径,但原理没有区别,因此解这类问题的最优选择当属bfs广度优先搜索。

使用bfs解题时,我们需要确定bfs起始条件,扩散规则以及bfs终止条件。与普通bfs题目不同,本题的难点就在于如何找到上述3个条件。首先题目给出了起点是左上角,因此,左上角坐标[0,0]一定是bfs起点之一,另外我们要知道,在不改变方向的前提下,从左上角能够到达的所有点与起点是同一级别的点,因为从起点到达这些点的花费都是0,因此我们可以将cost相同的点看做是同一级别的点,这些点也是我们bfs的起点。bfs每一步时,我们从这些点向外扩散一圈,能够覆盖到的点,以及与他们在同一级别上的所有点,都属于下一步bfs的范围,直到bfs范围能够覆盖到右下角位置,bfs的步数即是答案。

总结:

与普通的bfs不同,本题是将cost相同的所有点(利用题目给出的方向能够连接的所有点)看做为同一级别,这些点向外bfs扩散一圈,同时这一圈上所有的点以及与他们cost相同的点是bfs下一步的范围。这一点是本题最为精妙的地方!bfs每走一步,实际上是在级别不同的点之间做出了一次方向改变,使得他们级别相同。

实现代码:

boolean[][] visited; // 访问数组
// bfs的四个方向
int[][] dirs=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public int minCost(int[][] grid) {
    // 初始化访问数组
    visited=new boolean[grid.length][grid[0].length];
    // bfs用的Queue
    Queue<int[]> q = new LinkedList<>();
    // 将与右上角拥有相同cost的点加入Queue,作为bfs起点
    findSameCost(q,grid,0,0);
    // 返回结果
    int res=0;
    // bfs
    while(q.size()>0){
        // bfs每一步
        int size=q.size();
        while(size>0){
            size--;
            // 从Queue中取出一点
            int[] node = q.poll();
            // 如果该点是右下角,返回bfs步数
            if(node[0]==grid.length-1&&node[1]==grid[0].length-1){
                return res;
            }
            // 将当前点向四个方向扩散
            for(int[]d : dirs){
                // 得到扩散后的点坐标
                int row = node[0]+d[0];
                int col = node[1]+d[1];
                // 将扩散后的点以及与它在同一cost上的点加入道Queue中
                findSameCost(q,grid,row,col);
            }
        }
        // 步数加一
        res++;
    }
    return res;
}
// 找到与[row, col]为同一cost的所有点
void findSameCost(Queue<int[]> q,int[][] grid,int row,int col){
    // 当前坐标没有越界并且没有访问过
    while(row>=0&&row<grid.length
          &&col>=0&&col<grid[0].length
          &&!visited[row][col]){
        // 将当前节点设置为已访问
        visited[row][col]=true;
        // 将当前点加入到Queue
        q.offer(new int[]{row,col});
        // 获得当前点能够走到的下一点坐标
        int[] dir=dirs[grid[row][col]-1];
        row+=dir[0];
        col+=dir[1];
    }
}

本题解法执行时间为8ms。

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

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

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid-解题思路分析/
Categories: leetcode
kwantong: