算法：迷宫问题-递归实现

初始化迷宫

初始化一个8行7的二维数组。

maze := make([][7]int, 8)
//Print(maze)

for i := 0; i < 8; i++ {
    maze[i][0] = 1
    maze[i][6] = 1
    if i < 7 {
        maze[0][i] = 1
        maze[7][i] = 1
    }
}

maze[3][1] = 1
maze[3][2] = 1

得到迷宫如下

1   1   1   1   1   1   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   

递归寻找路径

人为定义算法：下 右 上 左 按此顺序走，若没走过则先置为2，再递归走下一步，若走过了或走不通则置为3。

func SetWay(maze [][7]int, i, j int) bool {
    if maze[6][5] == 2 {
        return true
    } else {
        if maze[i][j] == 0 {
            maze[i][j] = 2
            Print(maze)
            // 下 右 上 左
            if SetWay(maze, i+1, j) { // 往下
                return true
            } else if SetWay(maze, i, j+1) { // 往右
                return true
            } else if SetWay(maze, i-1, j) { // 往上
                return true
            } else if SetWay(maze, i, j-1) { // 往左
                return true
            } else {
                maze[i][j] = 3
                Print(maze)
                return false
            }
        } else {
            // 数值为1, 2, 3的情况都返回false
            return false
        }
    }
}

测试代码

// 初始化迷宫代码省略
SetWay(maze, 1, 1)

输出

1   1   1   1   1   1   1   
1   2   0   0   0   0   1   
1   2   2   0   0   0   1   
1   1   1   2   0   0   1   
1   0   0   2   0   0   1   
1   0   0   2   0   0   1   
1   0   0   2   2   2   1   
1   1   1   1   1   1   1

设置挡板

设置挡板帮助理解递归

func main() {
    maze := make([][7]int, 8)
    //Print(maze)

    for i := 0; i < 8; i++ {
        maze[i][0] = 1
        maze[i][6] = 1
    }

    for j := 0; j < 7; j++ {
        maze[0][j] = 1
        maze[7][j] = 1
    }

    maze[3][1] = 1
    maze[3][2] = 1

    maze[3][3] = 1
    maze[2][3] = 1
    maze[1][3] = 1


    Print(maze)

    SetWay(maze, 1, 1)

}

输出

1   1   1   1   1   1   1   
1   0   0   1   0   0   1   
1   0   0   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   0   1   0   0   1   
1   0   0   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   0   1   0   0   1   
1   2   0   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   0   1   0   0   1   
1   2   2   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   2   1   0   0   1   
1   2   2   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   3   1   0   0   1   
1   2   2   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   3   1   0   0   1   
1   2   3   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   2   3   1   0   0   1   
1   3   3   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------
1   1   1   1   1   1   1   
1   3   3   1   0   0   1   
1   3   3   1   0   0   1   
1   1   1   1   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   0   0   0   0   0   1   
1   1   1   1   1   1   1   
-------------------------