LeetCode(每日一题)-1391. 检查网格中是否存在有效路径

快来打我* 2023-09-29 08:30 4阅读 0赞

## LeetCode(每日一题)-1391. 检查网格中是否存在有效路径 ##

【**题目描述**】  
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid\[i\]\[j\] 的街道可以是：

*  1 表示连接左单元格和右单元格的街道。
 *  2 表示连接上单元格和下单元格的街道。
 *  3 表示连接左单元格和下单元格的街道。
 *  4表示连接右单元格和下单元格的街道。
 *  5 表示连接左单元格和上单元格的街道。
 *  6 表示连接右单元格和上单元格的街道。  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_19_color_FFFFFF_t_70_g_se_x_16]  
    你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。**该路径必须只沿着街道走**。

注意：你 不能变更街道。  
如果网格中存在有效的路径，则返回 true，否则返回 false 。  
示例 1：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_17_color_FFFFFF_t_70_g_se_x_16]

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

示例 2：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_17_color_FFFFFF_t_70_g_se_x_16 1]

输入：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  
    【**解题思路**】
 *  模拟行走
 *  可以通过dfs递归遍历，并且判断当前坐标是否能和上一个坐标街道连通，不能联通直接返回false  
    【**完整代码**】

public class Solution {
        
        int m,n;
        // 标记每个路径可以通的方向   0左1右2上3下
        static int[][] strees = {
        {
        },{
        0,1},{
        2,3},{
        0,3},{
        1,3},{
        0,2},{
        1,2}};
        // 移动 0左1右2上3下
        static int[] dx = {
        0,0,-1,1};
        static int[] dy = {
        -1,1,0,0};
        public boolean hasValidPath(int[][] grid) {
        
            m = grid.length;
            n = grid[0].length;
            return dfs(0,0,0,grid);
        }
        boolean dfs(int x,int y,int pre,int[][] grid){
        
            // 越界或者已经遍历过了
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0){
        
                return false;
            }
            // 获取当前格子的通路
            int[] stree = strees[grid[x][y]];
            // 判断和上一个是否存在通路，不存在直接返回false
            if(!check(pre,stree[0]) && !check(pre,stree[1])){
        
                return false;
            }
            // 存在通路，那么看看是否最后一个格子，是就直接返回true
            if (x == m - 1 && y == n - 1) {
        
                return true;
            }
            // 标记已经遍历过
            grid[x][y] = 0;
            for(int cur : stree){
        
                // 通过stree获取到下一个格子的坐标
                int nx = x + dx[cur];
                int ny = y + dy[cur];
                // 继续递归下一个节点
                if(dfs(nx,ny,cur,grid)){
        
                    return true;
                }
            }
            return false;
        }
        // 判断是否通路
        // pre == 0表示第一个格子 直接通过
        // pre + cur == 1 要是通路就必须存在一个通路是左，一个通路是右   0 + 1 = 1
        // pre + cur == 5 要是通路就必须存在一个通路是上，一个通路是下   2 + 3 = 
        boolean check(int pre,int cur){
        
            if(pre == 0){
        
                return true;
            }
            return pre + cur == 1 || pre + cur == 5;
        }
    
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3d6c52fe9cb34d9187473abe2eb5e7ee.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a3b533b9c25c45a184be1f7ff6e2187f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_17_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/e190cdc4580a44feadd06c0b5b7a5a5f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_17,color_FFFFFF,t_70,g_se,x_16