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

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

三月 22, 2020

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

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

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

注意：你 不能 变更街道。

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

我的思路

dfs查找，分6种情况，当前的是哪一种路，然后下一步要走哪一种路，如果不能走就不去搜索。第一次做这种题，代码还是很不好看的。一堆ifelse可以用switch优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Solution {
    public boolean hasValidPath(int[][] grid) {
        visited=new int[grid.length][grid[0].length];
        visited[0][0]=1;
        dfs(grid,0,0);
        // for(int i=0;i<visited.length;i++){
        //     for(int j=0;j<visited[i].length;j++){
        //         System.out.print(visited[i][j]+" ");
        //     }
        //     System.out.println();
        // }
        return flag;
    }
    public boolean flag=false;
    public int[][]visited;
    public void dfs(int[][]grid,int x,int y){
        //System.out.println("x "+x+"y "+y);
        if(x==grid.length-1&&y==grid[0].length-1){
            flag=true;
            return;
        }
        int[][]direction={{-1,0},{0,1},{1,0},{0,-1}};
        int now=grid[x][y];

        //////////////
        for(int i=0;i<4;i++){
            int nextX=x+direction[i][0];
            int nextY=y+direction[i][1];
            //System.out.println(nextX+" "+nextY);
            if(nextX<0||nextX>grid.length-1||nextY<0||nextY>grid[0].length-1)
              continue;
            int nextP=grid[nextX][nextY];
            if(now==1){
                if((i==0||i==2))
                continue;
                else{
                    if(i==1){
                        if(nextP==2||nextP==4||nextP==6)continue;
                    }else if(i==3){
                        if(nextP==2||nextP==3||nextP==5)continue;
                    }
                }
            }
            if(now==2){
                if((i==1||i==3))
                continue;
                else{
                    if(i==0){
                        if(nextP==1||nextP==5||nextP==6)continue;
                        
                    }else if(i==2){
                        if(nextP==1||nextP==3||nextP==4)continue;
                        
                    }
                }
            }
            if(now==3){
                if((i==0||i==1))
                continue;
                else{
                    if(i==2){
                        if(nextP==1||nextP==4)continue;
                    }else if(i==3){
                        if(nextP==2||nextP==5)continue;
                    }
                }
            }
            if(now==4){
                if((i==0||i==3))
                continue;
                else{
                    if(i==1){
                        if(nextP==2||nextP==6)continue;
                    }else if(i==2){
                        if(nextP==1||nextP==3)continue;
                    }
                }
            }
            if(now==5){
                if((i==2||i==1))
                continue;
                else{
                    if(i==0){
                        if(nextP==1||nextP==6)continue;
                    }else if(i==3){
                        if(nextP==2||nextP==3)continue;
                    }
                }
            }
            if(now==6){
                if((i==2||i==3))
                continue;
                else{
                    if(i==0){
                        if(nextP==1||nextP==5)continue;
                    }else if(i==1){
                        if(nextP==2||nextP==4)continue;
                    }
                }
            }
            if(visited[nextX][nextY]==1)
              continue;
            visited[nextX][nextY]=1;
            dfs(grid,nextX,nextY);
           }
       
    }
}

优化方法

评论区看到的检查网格中是否存在有效路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//定义四个方向，上下左右
    //建立形状和方向的映射
    int a[7][2] = {{0,0},{2,3},{0,1},{1,2},{1,3},{0,2},{0,3}};
    int n,m;
    bool visited[500][500];
    //判读顶点是否规范
    bool check(int x,int y){
        if(x < 0 || x >= m || y<0 || y >= n){
            return false;
        }
        return true;
    }
    void dfs(int x,int y,vector<vector<int>>& grid){
        if(check(x,y)==false) return;
        visited[x][y] = true;//标记访问
        // cout<<"x="<<x<<'\t'<<"y="<<y<<endl;
        int tmpdir = grid[x][y];//取出该点的街道类型
        for(int i=0;i<2;i++){
            int t = a[tmpdir][i];
            int tx = dir[t][0] + x;
            int ty = dir[t][1] + y;         
            //(tx,ty)是下一跳可到达的点。需要再去判读，该点是否和
            if(check(tx,ty)){
                // cout<<"tx="<<tx<<"\t"<<"ty="<<ty<<endl;
                int tmp = grid[tx][ty];//得到下一步的街道类型
                for(int k=0;k<2;k++){
                    int p = a[tmp][k];//得到该街道的两个方向
                    if(dir[t][0] + dir[p][0]==0 && dir[t][1]+dir[p][1]==0){//判读是否可以走通
                        if(!visited[tx][ty]){
                            dfs(tx,ty,grid);
                        }                    
                    }
                }                
            }
        }
    }
    bool hasValidPath(vector<vector<int>>& grid) {
        m = grid.size();//行数
        n = grid[0].size();//列数
        dfs(0,0,grid);
        if(visited[m-1][n-1] == true){
            return true;//可到达
        }
        return false;
    }
};

多用了一个数组表示当前的路的状态，再根据dir[t][0] + dir[p][0]==0 && dir[t][1]+dir[p][1]==0判断能不能再继续走。

这周的第三道题最后五分钟才写出来，还好也是三道题，基本目标达成了。
leetcode 63/100