X

LEETCODE 1391. Check if There is a Valid Path in a Grid 解题思路分析

题目大意:

检查网格中是否存在有效路径

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是:

  • 1 表示连接左单元格和右单元格的街道。
  • 2 表示连接上单元格和下单元格的街道。
  • 3 表示连接左单元格和下单元格的街道。
  • 4 表示连接右单元格和下单元格的街道。
  • 5 表示连接左单元格和上单元格的街道。
  • 6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发,网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意:你 不能 变更街道。

如果网格中存在有效的路径,则返回 true,否则返回 false 。

示例 1:

输入:grid = [[2,4,3],[6,5,2]]
输出:true
解释:如图所示,你可以从 (0, 0) 开始,访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2:

输入:grid = [[1,2,1],[1,2,1]]
输出:false
解释:如图所示,单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连,你只会停在 (0, 0) 处。

示例 3:

输入:grid = [[1,1,2]]
输出:false
解释:你会停在 (0, 1),而且无法到达 (0, 2) 。

示例 4:

输入:grid = [[1,1,1,1,1,1,3]]
输出:true

示例 5:

输入:grid = [[2],[2],[2],[2],[2],[2],[6]]
输出:true

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6

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

解题思路分析:

个人感觉这道题并没有什么可以分析的地方,只要细心肯定能做出来。

首先从左上角出发,左上角图形的状态决定了接下来我们能走向哪里,Street1只能走向右方(向左走越界),Street2和3只能向下走,Street4既可以向下走也可以向右走,Street5无路可走,Street只能向右走。理清了起点的方向之后,我们按照其路线一路走下去即可。当走到下一步时,我们先判断上一步是从哪里来,能不能与当前道路相连接,如果不能直接返回false。如果能,查看下一步能走向哪个方向。如果当前点是左下角的话,返回true,否则继续向后走。如果再达到左下角之前出现越界或者回路,证明不会再能够走向终点,此时返回false。

实现代码:

public boolean hasValidPath(int[][] grid) {
    if(grid.length==1&&grid[0].length==1) return true;
    int c=0,r=0,fromDir=0;
    switch(grid[0][0]){
        case 1:
        case 6:
            return dfs(grid,0,1,1);
        case 2:
        case 3:
            return dfs(grid,1,0,2);
        case 4:
            return dfs(grid,0,1,1)||dfs(grid,1,0,2);
        case 5:
            return false;
    }
    return false;
}
// fromDir: 1:left; 2:top; 3:right; 4:bottom
boolean dfs(int[][] grid,int r, int c, int fromDir){
    // 越界,返回false
    if(r==grid.length||c==grid[0].length||r<0||c<0) return false;
    int nextR=r, nextC=c, nextFromDir=fromDir;
    int current=grid[r][c];
    // 如果当前点以访问过,说明出现回路,返回false
    if(current==-1) return false;
    // 将当前点设为-1,代表已访问过
    grid[r][c]=-1;
    switch(fromDir){
        case 1: // 从左方到达当前点
            if(current==2||current==4||current==6){
                return false;
            }
            if(current==1){
                nextC=c+1;
                nextFromDir=1;
            }else if(current==3){
                nextR=r+1;
                nextFromDir=2;
            }else if(current==5){
                nextR=r-1;
                nextFromDir=4;
            }
            break;
        case 2: // 从上方到达当前点
            if(current==1||current==3||current==4){
                return false;
            }
            if(current==2){
                nextR=r+1;
                nextFromDir=2;
            }else if(current==5){
                nextC=c-1;
                nextFromDir=3;
            }else if(current==6){
                nextC=c+1;
                nextFromDir=1;
            }
            break;
        case 3: // 从右方到达当前点
            if(current==2||current==3||current==5){
                return false;
            }
            if(current==1){
                nextC=c-1;
                nextFromDir=3;
            }else if(current==4){
                nextR=r+1;
                nextFromDir=2;
            }else if(current==6){
                nextC=c+1;
                nextFromDir=1;
            }
            break;
        case 4: // 从下方到达当前点
            if(current==1||current==5||current==6){
                return false;
            }
            if(current==2){
                nextR=r-1;
                nextFromDir=4;
            }else if(current==3){
                nextC=c-1;
                nextFromDir=3;
            }else if(current==4){
                nextC=c+1;
                nextFromDir=1;
            }
            break;
    }
    if(r==grid.length-1&&c==grid[0].length-1) return true;
    return dfs(grid,nextR,nextC,nextFromDir);
}

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

Runtime: 6 ms, faster than 97.25% of Java online submissions for Check if There is a Valid Path in a Grid.

Memory Usage: 60.3 MB, less than 100.00% of Java online submissions for Check if There is a Valid Path in a Grid.

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