迷宫结构文件：
6 5
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
注意在 WIN10 中golang中fscanf读取文件时把回车替换成0 这时要把换行符切换到 LF
上代码
package main
import (
"fmt"
"os"
)
func main() {
maze := readMaze("maze/maze.in")
//walk this maze
steps := walk(maze,point{0,0}, point{len(maze)-1 , len(maze[0])-1})
//print the trace
for _,row := range steps {
for _, val := range row{
fmt.Printf("%3d",val)
}
fmt.Println()
}
}
/**
read maze.in file, generate slice of [][]int
*/
func readMaze(filename string) [][]int{
file,err := os.Open(filename)
if err != nil{
panic(err)
}
var row,col int
fmt.Fscanf(file,"%d %d", &row, &col)
// this is gnerating a slice of []int, so write as [][]int
maze := make([][]int, row)
for i:=range maze{
maze[i] = make([]int,col)
for j:= range maze[i]{
fmt.Fscanf(file, "%d",&maze[i][j])
}
}
return maze
}
/**
点的结构体
*/
type point struct {
i,j int
}
/*
方向是左下右上4个
*/
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}
}
/*
判断两点：
1：点是否超界了
2：是否在grid里面， 这个grid即可以是迷宫，也可以是后面用来记录轨迹的图
*/
func (p point) at (grid [][]int)(int, bool){
//p.i<0説明p点的列超出了左边界
//p.i>=len(grid)説明p点的列超出了右边界
if p.i<0 || p.i>=len(grid){ return 0,false }
//p.i<0説明p点的列超出了上边界
//p.i>=len(grid)説明p点的列超出了下边界
if p.j<0 || p.j>=len(grid[p.i]){ return 0,false}
return grid[p.i][p.j],true
}
/*
走迷宫的函数，
返回 [][]int , 返回一个路径
*/
func walk(maze [][]int, start point , end point)[][]int{
// 建立一个slice，尺寸和maze一样，但是没有值的二维数组
steps := make([][]int , len(maze))
for i:= range steps{
steps[i] = make([]int, len(maze[i]))
}
// 初始化队列 数组 加入起始坐标：star
// Q是数组， 这是数组添加元素的语法
Q := []point{start}
// 如果还有可以走的，则Q数组就有值，那就走下去
for len(Q) > 0 {
// 总是从数组的头取 实现先进先出的队列
cur := Q[0]
// 然后把上面走过的那走的那个点去掉
Q = Q[1:]
// 到达终点
if cur == end {
break
}
// 上下左右走 如果可以走的话把那个点加入队列
for _,dir := range dirs{
// 计算走后的坐标点
next := cur.add(dir)
// val ==1 说明是墙
val,ok := next.at(steps)
if !ok || val == 1{ continue}
// 看看steps表， 是否这个点在这个轨迹里面，
val,ok = next.at(steps)
//如果走过
if !ok || val != 0{
continue
}
// 如果是开始点也不走
if next == start {
continue
}
// 出发点的值
curStepsValue ,_ := cur.at(steps)
// 在轨迹图里面记下这个点，并把这个点的值+1
steps[next.i][next.j] = curStepsValue +1
// 加入队列
Q = append(Q,next)
}
}
return steps
}
Processed:
0.014, SQL:
9
