1391. 检查网格中是否存在有效路径【深度优先搜索DFS】

题目

题目
题目
示例1
示例2-5.png
提示

思路

从格子[0,0]开始，进行dfs，看看是否能到达最后一个节点？
如何标记该节点是否已经访问？grid[][]中取值范围都是1~6，可以将进行过dfs的节点标记为0。
如何标记进行dfs？从[0,0]开始，判断与周边的节点的连通性。如果连通，则对相邻节点进行dfs，这是一个递归的过程。
函数结束后，如果最后一个节点grid[][]的值为0，说明从[0][0]到该节点是连通的。

代码

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

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

// 解题思路
// 解题思路
// 1、从[0,0]开始dfs
// 2、遍历过的节点的值置为0防止重复遍历；
// 3、满足下面条件之一，则继续dfs
//     当存在向上的接口 && 上方节点存在向下接口；
//     当存在向下的接口 && 下方节点存在向上接口；
//     当存在向左的接口 && 左侧节点存在向右接口；
//     当存在向右的接口 && 右侧节点存在向左接口；
// 4、返回最后一个节点是否遍历过(即是否为0)

// grid = [[1,2,1],[1,2,1]]
// grid中的值的范围是1-6，因此可以复用这个grid，访问grid[0][0]的时候，将其置0（表示已经访问）
// 对上下左右进行dfs
// 如果最后一个节点的值最后为0，说明与[0][0]是连通的！
func hasValidPath(grid [][]int) bool {
    dfs(grid, 0, 0)
    //fmt.Printf("dfs is\n %v\n\n", grid)
    return grid[len(grid)-1][len(grid[0])-1] == 0
}

// 输入1~6，输入方向；
// 输出该方向是否有接口
type Direction uint8
const(
    DirUp Direction = iota
    DirDown
    DirLeft
    DirRight
)

var dirMatrix = [7][4]bool{
    {false, false, false, false},   // 0凑数的
    {false, false, true, true},     // 1 表示连接左单元格和右单元格的街道。
    {true, true, false, false},     // 2 表示连接上单元格和下单元格的街道。
    {false, true, true, false},     // 3 表示连接左单元格和下单元格的街道。
    {false, true, false, true},     // 4 表示连接右单元格和下单元格的街道。
    {true, false, true, false},     // 5 表示连接左单元格和上单元格的街道。
    {true, false, false, true},     // 6 表示连接右单元格和上单元格的街道。
}

// 数字num在方向dir上是否有入口
func hasEntrance(num int, dir Direction) bool {
    if num < 1 || num > 6 {
        return false
    }

    return dirMatrix[num][dir]
}

// grid既作为输入参数，也作为是否访问的标记
// row行，col列，表示当前对那个节点进行dfs
func dfs(grid [][]int, row, col int) {
    // 递归停止条件
    if grid[row][col] == 0 {
        return
    }

    num := grid[row][col]
    grid[row][col] = 0 // 标记该点已经被访问了

    // 如果不是第1行
    if row > 0 && hasEntrance(num, DirUp) && hasEntrance(grid[row-1][col], DirDown) {
        dfs(grid, row-1, col)
    }

    // 如果不是最后1行
    if row < len(grid)-1 && hasEntrance(num, DirDown) && hasEntrance(grid[row+1][col], DirUp) {
        dfs(grid, row+1, col)
    }

    // 如果不是第1列
    if col > 0 && hasEntrance(num, DirLeft) && hasEntrance(grid[row][col-1], DirRight) {
        dfs(grid, row, col-1)
    }

    // 如果不是最后1列(len(grid[0])注意边界条件)
    if col < len(grid[0]) -1 && hasEntrance(num, DirRight) && hasEntrance(grid[row][col+1], DirLeft) {
        dfs(grid, row, col+1)
    }
}