go语言使用面向对象方式实现迷宫广度优先算法，让你体验比诗还优雅的代码

go语言使用面向对象方式实现迷宫广度优先算法，让你体验比诗还优雅的代码

package main

import (
    "fmt"
)

// point 表示地图上的一个点
type point struct {
    x, y int
}

// Map 表示地图和相关信息
type Map struct {
    M         [][]int // 地图数据
    resultMap [][]int // 结果地图
    routesMap [][]int // 路径地图

    rows int // 行数
    clos int // 列数
    step int // 步数

    curPoint *point   // 当前点
    routes   []*point // 路径点集合
    waitFind []*point // 待寻找点集合
    start    *point   // 起点
    end      *point   // 终点
}

// NewMap 创建一个新的地图
func NewMap(param *Map) (*Map, error) {
    if len(param.M) == 0 || len(param.M[0]) == 0 {
       return nil, fmt.Errorf("数据不能为空")
    }
    rows := len(param.M)
    cols := len(param.M[0])
    resultMap := make([][]int, rows)
    for k := range resultMap {
       resultMap[k] = make([]int, cols)
    }
    routesMap := make([][]int, rows)
    for k := range routesMap {
       routesMap[k] = make([]int, cols)
    }
    return &Map{
       M:         param.M,
       resultMap: resultMap,
       routesMap: routesMap,
       rows:      rows,
       clos:      cols,
       step:      1,
       curPoint:  &point{},
       routes:    []*point{{}},
       waitFind:  []*point{{}},
       start:     &point{},
       end: &point{
          x: cols,
          y: rows,
       }, // 终点
    }, nil
}

// Start 开始寻找路径
func (m *Map) Start() *Map {
    for {
       waitFind := m.waitFind
       m.waitFind = []*point{}
       for _, m.curPoint = range waitFind {
          if m.curPoint.x == m.end.x && m.curPoint.y == m.end.y {
             return m
          }
          m.findStep()
       }
       if len(m.waitFind) == 0 {
          for _, v := range m.routes {
             m.resultMap[v.y][v.x] = 1
          }
          return m
       }
       m.step++
    }
}

// findStep 寻找下一步
func (m *Map) findStep() {
    if p := m.goUp(); p != nil {
       m.routesMap[p.y][p.x] = m.step
       m.routes = append(m.routes, p)
       m.waitFind = append(m.waitFind, p)
    }
    if p := m.goLeft(); p != nil {
       m.routesMap[p.y][p.x] = m.step
       m.routes = append(m.routes, p)
       m.waitFind = append(m.waitFind, p)
    }
    if p := m.goDown(); p != nil {
       m.routesMap[p.y][p.x] = m.step
       m.routes = append(m.routes, p)
       m.waitFind = append(m.waitFind, p)
    }
    if p := m.goRight(); p != nil {
       m.routesMap[p.y][p.x] = m.step
       m.routes = append(m.routes, p)
       m.waitFind = append(m.waitFind, p)
    }
}

// routesIsExist 判断路径是否存在
func (m *Map) routesIsExist(p *point) bool {
    for _, v := range m.routes {
       if v.y == p.y && v.x == p.x {
          return true
       }
    }
    return false
}

// isOne 判断是否为障碍物
func (m *Map) isOne(p *point) bool {
    return m.M[p.y][p.x] == 1
}

// notCanStep 判断是否无法前进
func (m *Map) notCanStep(p *point) bool {
    return m.routesIsExist(p) || m.isOne(p)
}

// goUp 向上移动
func (m *Map) goUp() *point {
    if m.curPoint.y-1 < 0 {
       return nil
    }
    p := &point{
       x: m.curPoint.x,
       y: m.curPoint.y - 1,
    }
    if m.notCanStep(p) {
       return nil
    }

    return p
}

// goLeft 向左移动
func (m *Map) goLeft() *point {
    if m.curPoint.x-1 < 0 {
       return nil
    }
    p := &point{
       x: m.curPoint.x - 1,
       y: m.curPoint.y,
    }
    if m.notCanStep(p) {
       return nil
    }

    return p
}

// goRight 向右移动
func (m *Map) goRight() *point {
    if m.curPoint.x+1 > m.clos-1 {
       return nil
    }
    p := &point{
       x: m.curPoint.x + 1,
       y: m.curPoint.y,
    }
    if m.notCanStep(p) {
       return nil
    }

    return p
}

// goDown 向下移动
func (m *Map) goDown() *point {
    if m.curPoint.y+1 > m.rows-1 {
       return nil
    }
    p := &point{
       x: m.curPoint.x,
       y: m.curPoint.y + 1,
    }
    if m.notCanStep(p) {
       return nil
    }

    return p
}

// printResult 打印结果地图
func (m *Map) printResult() *Map {
    for _, v := range m.resultMap {
       fmt.Println(v)
    }
    return m
}

// printRoutes 打印路径地图
func (m *Map) printRoutes() *Map {
    fmt.Println()
    for _, v := range m.routesMap {
       for _, vv := range v {
          fmt.Printf("%4d", vv)
       }
       fmt.Println()
    }
    return m
}

var (
    // maps 地图数据
    maps = [][]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},
    }
)

func main() {
    m, err := NewMap(&Map{M: maps})
    if err != nil {
       fmt.Println(err)
       return
    }
    m = m.Start().printResult().printRoutes()
}

   0   0   4    5     6

   1   2   3    0     7

   2   0   4    0     8

   0   0   0   10    9

   0   0  12  11    0

   0   0  13  12  13

结果如上