手动走迷宫

命令行输入方向，控制1到迷宫出口

package main import "fmt" // M 表示 纵， N 横 const M, N = 11, 10 var ymove, xmove int = 0, 0 // 人开始位置：ymove 就是上下[M]，xmove就是左右[N] //1代表人，2代表障碍，0空地 var data [M][N]int =[M][N]int{ { 1, 0, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 2, 0, 0, 2, 0, 0, 0 }, { 0, 0, 0, 0, 2, 0, 0, 2, 2, 0 }, { 0, 0, 0, 0, 2, 0, 2, 0, 0, 0 }, { 0, 0, 0, 0, 2, 0, 0, 0, 0, 2 }, { 2, 2, 2, 0, 0, 2, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 2, 0, 2 }, { 0, 0, 0, 0, 0, 0, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 2, 2, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 2, 0 }, } // 显示迷宫 func Show() { fmt.Println("-----------------------------------------------") for i := 0; i < M; i++{ for j := 0; j < N; j++ { fmt.Printf("%5d", data[i][j]) } fmt.Println() } } // 每一次位置移动： 相对于当前位置，可以往”上(s)、下(x)、左(z)、右(y)“四个位置走 func run(direct string) { if direct == "s"{ //上，下 改变的是ymove，ymove与 M有关 // ymove - 1 >= 0 表示上面还有位置。 data[ymove - 1][xmove] != 2表示上面不是障碍 if ymove - 1 >= 0 && data[ymove - 1][xmove] != 2 { data[ymove - 1][xmove], data[ymove][xmove] = data[ymove][xmove], data[ymove - 1][xmove] // 交换位置 ymove-- } }else if (direct == "x"){ if ymove + 1 <= M - 1 && data[ymove + 1][xmove] != 2 { data[ymove + 1][xmove], data[ymove][xmove] = data[ymove][xmove], data[ymove + 1][xmove] ymove++ } }else if (direct == "z"){ if xmove - 1 >= 0 && data[ymove][xmove - 1] != 2 { data[ymove][xmove - 1], data[ymove][xmove] = data[ymove][xmove], data[ymove][xmove - 1] xmove-- } }else if(direct == "y"){ if xmove + 1 <= N - 1 && data[ymove][xmove + 1] != 2 { data[ymove][xmove + 1], data[ymove][xmove] = data[ymove][xmove], data[ymove][xmove + 1] xmove++ } }else{ fmt.Println("不知道的方向，不可以走") } } func main() { Show() for { var str string fmt.Scanln(&str) run(str) Show() } }

走迷宫自动

相对于当前位置，一般有四个方向走，因为我们要从左上角 —》 右下角。 因此规定优先“右”， “下”， “上”， “左”迷宫可以看成是一棵四叉树。相当于四叉树的深度遍历。递归可以用栈实现

递归

package main import ( "fmt" ) // M 表示 纵， N 横 const M, N = 10, 10 var cangoout bool = false //1代表人，2代表障碍，0空地 var data [M][N]int =[M][N]int{ { 1, 0, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 2, 0, 0, 2, 0, 0, 0 }, { 2, 0, 0, 0, 2, 0, 0, 2, 2, 0 }, { 0, 2, 0, 0, 2, 0, 2, 0, 0, 0 }, { 0, 2, 0, 2, 2, 0, 0, 0, 0, 2 }, { 2, 2, 2, 2, 2, 2, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 2, 0, 2 }, { 0, 0, 0, 0, 0, 0, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 2, 2, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, } // 显示迷宫 func Show() { fmt.Println("-----------------------------------------------") for i := 0; i < M; i++{ for j := 0; j < N; j++ { fmt.Printf("%5d", data[i][j]) } fmt.Println() } } func FoundOut(imove int, jmove int) { data[imove][jmove] = 3 Show() if imove == M - 1 && jmove == N - 1 { cangoout = true return }else{ // 注意不是else if， 而是if /* * else if 只要有一个分支执行了，另外的分支就不执行了 */ if jmove + 1 < N && data[imove][jmove + 1] == 0 && cangoout == false { // 右 FoundOut(imove , jmove + 1) } if imove + 1 < M && data[imove + 1][jmove] == 0 && cangoout == false { // 下 FoundOut(imove + 1, jmove) } if imove - 1 > -1 && data[imove - 1][jmove] == 0 && cangoout == false { // 上 FoundOut(imove - 1, jmove) } if jmove - 1 > -1 && data[imove][jmove - 1] == 0 && cangoout == false { // 右 FoundOut(imove , jmove - 1) } } } func main() { FoundOut(0, 0) Show() fmt.Println(cangoout) }

(0, 0)出栈后，整个递归过程也结束了。

此时canout = false，也就是迷宫是不能解决的

版本二

从上面我们可以看出，递归函数的调用相当于压栈，出栈，因此我们也可以把上面改成栈实现

实现栈

实现栈

栈走迷宫

package main import ( "fmt" ) // M 表示 纵， N 横 const M, N = 10, 10 //1代表人，2代表障碍，0空地 var data [M][N]int =[M][N]int{ { 1, 0, 2, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 2, 0, 0, 2, 0, 0, 0 }, { 2, 0, 0, 0, 2, 0, 0, 2, 2, 0 }, { 0, 2, 0, 0, 2, 0, 2, 0, 0, 0 }, { 0, 2, 0, 2, 2, 0, 0, 0, 0, 2 }, { 2, 2, 2, 2, 2, 2, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 2, 0, 2 }, { 0, 0, 0, 0, 0, 0, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 2, 2, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, } // 显示迷宫 func Show() { fmt.Println("-----------------------------------------------") for i := 0; i < M; i++{ for j := 0; j < N; j++ { fmt.Printf("%5d", data[i][j]) } fmt.Println() } } type Pos struct { imove, jomve int } /* 相对于当前位置，一直往右边走，直到右边不通。 那么往下面走， 直到下边不通。 那么往上边左，直到上边不通。那么往左边走，直到左边不通。 如果四个方向都不通， 那么回退到上一个位置。 */ func FoundOut() bool { stack := NewStack() p := Pos{ imove: 0, jomve: 0, } _ = stack.Push(p) for !stack.IsEmpty() { Show() pop, _ := stack.Peek() // 获取栈顶元素 p := (pop).(Pos) data[p.imove][p.jomve] = 3 // 标记当前位置走过了 if p.jomve == N - 1 && p.imove == M - 1 { // 判断是不是到了终点 return true } // 右边走 if p.jomve + 1 < N && data[p.imove][p.jomve + 1] == 0 { // 判断右边是不是还有位置 _ = stack.Push(Pos{ imove: p.imove, jomve: p.jomve + 1, }) // 压栈 continue } // 下边 if p.imove + 1 < M && data[p.imove + 1][p.jomve] == 0 { // 判断下边是不是还有位置 _ = stack.Push(Pos{ imove: p.imove + 1, jomve: p.jomve, }) // 压栈 continue } // 上边 if p.imove - 1 > -1 && data[p.imove - 1][p.jomve] == 0 { // 判断上边是不是还有位置 _ = stack.Push(Pos{ imove: p.imove - 1, jomve: p.jomve, }) // 压栈 continue } // 左边 if p.jomve - 1 > -1 && data[p.imove][p.jomve - 1] == 0 { // 判断左边是不是还有位置 _ = stack.Push(Pos{ imove: p.imove, jomve: p.jomve - 1, }) // 压栈 continue } stack.Pop() // 四个方向都不通，那么弹出栈顶元素 } return false } func main() { FoundOut() Show() }