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
结果如上
发表评论