GO广度优先算法——迷宫

GO
小编16990

广度优先算法

节点状态：

1、[已经发现，已探索]

2、[已发现，未探索]

3、[未发现，未探索]

相较于深度优先算法，广度优先算法须遍历完节点所有方向，才能进行下一步探索。

方向  建议上左下右（逆时针）

一、用循环创建二维slice

maze :=make([][]int,row)
for i:=range maze{
   maze[i] =make([]int,col)
}

二、使用slice来实现队列

steps :=make([][]int,len(maze))
for i :=range steps {
   steps[i] = make([]int, len(maze[i]))
   }
Q :=[]point{start}
for len(Q)>0  {
   cur :=Q[0]
   Q =Q[1:]
   if cur==end{
      break
   }
for _,dir :=range dirs {
   next :=cur.add(dir)

   val,ok :=next.at(maze)
   if !ok ||val ==1{
      continue
   }
   val,ok=next.at(steps)
   if !ok ||val !=0{
      continue
   }
   if next ==start{
      continue
   }
   curSteps,_:=cur.at(steps)
   steps[next.i][next.j]=curSteps+1

   Q=append(Q,next)

}

三、用Fscanf读取文件

fmt.Fscanf(file,"%d",&maze[i][j])

四、对Point的抽象

//创建 point结构
type point struct {
   i,j int
}
//构建point add方法
func (p point)add(r point) point {
   return point{p.i+r.i,p.j+r.j}
}
Tagged