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

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

```输入：grid = [[2,4,3],[6,5,2]]

```输入：grid = [[1,2,1],[1,2,1]]

```输入：grid = [[1,1,2]]

```输入：grid = [[1,1,1,1,1,1,3]]

```输入：grid = [[2],[2],[2],[2],[2],[2],[6]]

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

```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);
}```

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.