go语言实现迷宫广度优先算法 ​

go语言实现迷宫广度优先算法

package main

import (
   "fmt"
   "strconv"
   "strings"
)

type orders struct {
   x int
   y int
}

var (
   order = []orders{
      //{x: 0, y: 1},
      //{x: 0, y: 2},
   }
   start = orders{
      x: 0,
      y: 0,
   }
   already = []orders{
      {start.x, start.y},
   }

   end = orders{
      x: 4,
      y: 5,
   }
   maze = [][]int{
      {0, 1, 0, 0, 0},
      {0, 0, 0, 1, 0},
      {0, 1, 0, 1, 0},
      {1, 1, 1, 0, 0},
      {0, 1, 0, 0, 1},
      {0, 1, 0, 0, 0},
   }

   step    = map[string]int{"0,0": 0}
   stepnum = 1

   canStop = false
)

func next() {
   for _, node := range order {
      fmt.Println(node.x, node.y)
   }
}

//探索一轮
func explore(o orders) {

   os := []orders{
      {x: o.x, y: o.y - 1}, //上
      {x: o.x - 1, y: o.y}, //左
      {x: o.x, y: o.y + 1}, //下
      {x: o.x + 1, y: o.y}, //右
   }

   for _, v := range os {
      if v.y < 0 || v.x < 0 || v.y >= len(maze) || v.x >= len(maze[0]) {
         continue
      }

      stepKey := fmt.Sprintf("%d,%d", v.x, v.y)
      _, ok := step[stepKey]

      if maze[v.y][v.x] == 0 && !ok { //判断当前坐标是否能收集
         step[stepKey] = stepnum //当前坐标是第几步

         already = append(already, orders{x: v.x, y: v.y})
         order = append(order, orders{x: v.x, y: v.y})

         if v.x == end.x && v.y == end.y {
            canStop = true
         }
      }
   }
   if len(order) == 0 {
      canStop = true
   }
}
func outputMaze(ma [][]int) {
   for _, v := range ma {
      for _, vv := range v {
         fmt.Printf("%3d ", vv)
      }
      fmt.Println()
   }
   fmt.Println()
   fmt.Println()
}

func findPath(st [][]int) (path map[int]orders) {
   o := end
   path = make(map[int]orders, stepnum)
   path[stepnum] = o
   for i := stepnum; i != 0; {
      onum := st[o.y][o.x]
      os := []orders{
         {x: o.x, y: o.y - 1}, //上
         {x: o.x - 1, y: o.y}, //左
         {x: o.x, y: o.y + 1}, //下
         {x: o.x + 1, y: o.y}, //右
      }
      for _, v := range os {
         if v.y < 0 || v.x < 0 || v.y >= len(st) || v.x >= len(st[0]) {
            continue
         }
         if st[v.y][v.x] == onum-1 {
            o = orders{x: v.x, y: v.y}
            path[st[v.y][v.x]] = o
            i = st[v.y][v.x]
            break
         }
      }
   }

   return path
}

func main() {
   outputMaze(maze)
   explore(start)

   for !canStop {
      stepnum++
      for _, v := range order {
         order = order[1:]
         explore(v)
      }
   }

   step2 := make([][]int, len(maze))
   for k := range step2 {
      step2[k] = make([]int, len(maze[0]))
   }

   //for i := stepnum; i > 0; i-- {
   // fmt.Println(step[])
   //}

   for k, v := range step {
      arr := strings.Split(k, ",")
      a, b := arr[0], arr[1]
      x, _ := strconv.Atoi(a)

      y, _ := strconv.Atoi(b)

      step2[y][x] = v
   }

   outputMaze(step2)

   path := findPath(step2)
   fmt.Println(path)

}

go语言实现迷宫广度优先算法 运行结果：