迷宫,只可以上下左右走,要求从左上角到右下角到最短路径
6 6
0 1 0 0 1 0
0 0 0 1 0 0
0 1 0 0 0 0
0 1 1 0 1 0
1 0 0 0 0 1
1 1 0 0 0 0
解题思路
- 获取迷宫图,由左到右 由上到下标点(如:[0,0])
- 从入口点开始走一步(上下左右),列出所有可能的下一步 加入队列,并在迷宫图上标记
- 一直走,知道走到当前点等于结束点
go语言解法
package main
import (
"fmt"
"os"
)
// 获取迷宫图
func readBfs(filename string) [][]int {
file, err := os.Open(filename)
if err != nil {
panic(err)
}
var row, col int
fmt.Fscanf(file,"%d %d",&row, &col) //读取前两个数字,赋值给row col
bfs := make([][]int,row) // 6行
for i := range bfs {
bfs[i] = make([]int,col) //6列
for j := range bfs[i] {
fmt.Fscanf(file, "%d", &bfs[i][j])
}
}
return bfs
}
// 定义点的结构 (当前点,下一点)
type point struct {
i, j int
}
// 定义上左下右四步
var dirs = [4]point {
{-1,0}, {0,-1},{1,0},{0,1}
}
// 点移动到下一点到位置
func (p point) add(r point) point {
return point{p.i+r.i,p.j+r.j}
}
// 判断点是否在迷宫途中,在就返回迷宫图对应到点值,不再返回false
func (p point) at(grid [][]int) {int, bool} {
if p.i < 0 || p.i >= len(gird) {
return 0,false
}
if p.j < 0 || p.j >= len(grid[p.i]) {
return 0,false
}
return grid[p.i][p.j],true
}
// 返回走过的步骤图
func walk(bfs [][]int, start, end point) [][]int {
steps := make([][]int, len(bfs))
for i := range bfs {
steps[i] = make([]int, len(bfs[i]))
}
queue := []point{start} //入口加入队列
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
if cur == end { //走到出口
break
}
for _,dir := range dirs {
next := cur.add(dir)
val, ok := next.at(bfs)
if !ok || val == 1 {
continue
}
if next == start {
continue
}
curStep, _ := cur.at(steps)
steps[next.i][next.j] = curStep + 1
queue = append(queue, next)
}
}
return steps
}
func main() {
bfs := readBfs("bfs/bfs.ini")
steps := walk(bfs, point{0,0},point{len(bfs)-1,len(bfs[0])-1})
for _, row := range steps {
fmt.Println(row)
}
}