用go实现迷宫问题

落日映苍穹つ 2021-07-24 16:57 324阅读 0赞

# 一 需求 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

求从A到B的路径。

# 二 代码 #

package main
    
    import (
       "fmt"
    )
    
    // 完成走迷宫找路
    // myMap *[8][7]int：地图，保证是同一个地图，使用引用
    // i,j：表示对地图的哪个点进行测试
    func SetWay(myMap *[8][7]int, i int, j int) bool {
       // 找到路的情况
       if myMap[6][5] == 2 {
          return true
       } else {
          // 没找到路，要继续找
          if myMap[i][j] == 0 { // 如果这个点是可以探测
             // 假设这个点是可以通, 还需要探测上下左右
             //使用策略：下右上左
             myMap[i][j] = 2
             if SetWay(myMap, i+1, j) { // 下
                return true
             } else if SetWay(myMap, i, j+1) { // 右
                return true
             } else if SetWay(myMap, i-1, j) { // 上
                return true
             } else if SetWay(myMap, i, j-1) { // 左
                return true
             } else { // 死路
                myMap[i][j] = 3
                return false
             }
          } else { // 说明这个点不能探测，为1，是墙
             return false
          }
       }
    }
    
    func main() {
       // 先创建一个二维数组，模拟迷宫
       // 规则
       // 1 如果元素的值为1，就是墙
       // 2 如果元素的值为0，是没有走过的点
       // 3 如果元素的值为2，是一个通路
       // 4 如果元素的值为3，是走过的点，但是走不通
       var myMap [8][7]int
       // 先把地图的最上和最下设置为1，表示墙
       for i := 0; i < 7; i++ {
          myMap[0][i] = 1
          myMap[7][i] = 1
       }
       // 再把地图的最左和最右设置为1，表示墙
       for i := 0; i < 8; i++ {
          myMap[i][0] = 1
          myMap[i][6] = 1
       }
       // 其他墙设置
       myMap[3][1] = 1
       myMap[3][2] = 1
       // 输出地图
       for i := 0; i < 8; i++ {
          for j := 0; j < 7; j++ {
             fmt.Print(myMap[i][j], " ")
          }
          fmt.Println()
       }
       // 走迷宫
       SetWay(&myMap, 1, 1)
       fmt.Println("探测完毕....")
       // 输出地图走法
       for i := 0; i < 8; i++ {
          for j := 0; j < 7; j++ {
             fmt.Print(myMap[i][j], " ")
          }
          fmt.Println()
       }
    }

# 三 测试 #

> 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
> 
> 探测完毕....
> 
> 1 1 1 1 1 1 1
> 
> 1 2 0 0 0 0 1
> 
> 1 2 2 2 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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/1b6971b3b07e4a22a04f9d10c842dd80.png