假设有一个迷宫 由 1 0 组成 1代表墙 0代表可以走通

用文本记录

6 6
0 1 0 0 0 0
0 0 0 1 0 0
0 1 0 1 0 1
1 1 1 0 0 1
0 1 0 0 1 0
0 1 0 0 0 1

前一行记录了 行数6 和 列数 6

用GO语言读取 上述格式的文件

//打开文件
file,err := os.Open(finlename)
//Go语言万能错误处理语句
if(err != nil){
	panic(err)
}
//定义变量 记录 行列
var row,col int
//给定扫描文本 按照指定格式 读出变量 赋值给变量
fmt.Fscanf(file,"%d %d",&row,&col)
//声明 row大小的 []int类型 切片数组
maze := make([][]int,row)
//按索引遍历 切片
for i:= range maze{
	//声明 col 大小的 int类型 切片数组
	maze[i] = make([]int,col)
	//循环遍历 int数组切片
	for j := range maze[i]{
		//扫描数组 按照 %d 格式 去数组内容 赋值给 maze切片
		fmt.Fscanf(file,"%d",&maze[i][j])
	}
	//返回切片数组
	return maze
}

要想找到迷宫出口 name你就需要遍历迷宫
那么遍历迷宫你需要做什么
拆分成以下几步

1. 首先你得站在 当前这个位置 去尝试上下左右的走
2. 每次上下左右后 你先得看看 你是否还在这个迷宫内 索引直接为负 或者超出地图最大大小(如果边缘 没有设置墙(1)的情况下 你相当于就直接穿出了这个迷宫 )
3. 你自己需要维护一份一样大小的地图 记录你从哪个点走的每一步的上一步是什么 走了几步(电视剧里 经常会出现的场景 你进入了一个森林 迷路了 然后拿起一块石头刻在树上 然后来寻找路 )
4. 然后你需要看看 你走的路是否是以前走过的路 走过了 那是自然不可能再去走的(要不然就会是一个死循环了) 就不走这一步了 还有这一步 回到了原点也不能走。
5. 当你上下左右走了之后 找到了下一步 那么 你可以自己记录下 这一步的部树 当然你可能找到 上下左右 不同方向都可以走 那么 此时 你就先记下 下左右 其他方向 等以后再走 先把上方向先尝试下 这就是深度优先的思想。

那么按照上面讲的 定义以下 你要上下走动的数据结构
假设 一张66的方格地图 如果你处于 11 (行 * 列)的坐标
你向下走一步此时 你是 多少呢?
那么不就是 行 +1 ,列不变= 2 * 1 吗
那么下移 就是 原坐标+(1,0)
上移动呢 那不是很简单了吗 原坐标+(-1,0)
同理 左移 原坐标+(0,-1)
同理 右移 原坐标+(0,1)
那么数据结构就出来了

//定义 用来记录x坐标 和 y 坐标的2个整数
type point struct {
	x, y int
}
//定义了 上下左右操作 的数组 
var dirs =[4]point{
	//向上走一步
	{-1,0},
	//向左走一步
	{0,-1},
	//向下走一步
	{1,0},
	//向右走一步
	{0,1},
}

那么 定义好了上下左右数据结构 接下来我们要上下左右的走 需要计算走了之后的坐标 坐标数据结构 需要一个方法执行计算 坐标 很简单直接x坐标相加 y坐标相加

//坐标的数据结构 相加计算
func (p point) add(r point) point{
	return point{p.x + r.x,p.y + r.y}
}

那么当我们 走了一步后 需要按照上面所说的第二步 判断下自己 是不是还在地图里面 当执行了 假设你在 0行 0列 (假设索引从0开始) 向上走了一步 不就成了-1行 0列 或者 6* 6 的 地图 你在 5行0列(索引0开始) 向下 add 了 一行 6行0列 你又 走出了地图 那么这样就没什么意义了 这个向下的点 就行不通
下面就是判断 是否小于0 或者大于地图最大大小

func (p point) at (grid [][]int) (int,bool){
	//如果判断x坐标已经超出 上边界 或者下边界 则 返回false
	if p.x < 0 || p.x >= len(grid){
		return 0,false
	}
	// 如果判断y坐标已经超出 上边界 或者下边界 则 返回false
	if p.y < 0 || p.y >= len(grid[p.x]){
		return 0,false
	}
	//如果在地图里就返回 true 
	return grid[p.x][p.y],true
}

那么接下来 就要定义一个方法 去 遍历上下左右的走 需要记住的是 你每次走 都是 在当前点上 去上下左右 走 然后记录下 这四个点 哪几个点是可以走的点 然后先记录下来 相当于放到队列里。这个队列 是先进先出的。 每次去队列里找 有没有 可以走的点 直到 没有可以走的点为止

注意几点: 维护一份自己的地图 和 迷宫 大小 是一样的 初始化 为0 然后 每一次走到下一个点的是否在 索引为上一个点 加 1

func walk(maze [][]int,start,end point) [][]int{
	//自己的地图
	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:]
		//上下左右走 如果走的同把那个点加入到队列
		for _,dir := range dirs{
			//计算走后的坐标点
			next := cur.add(dir)
			//判断是否超界 判断是否 是 1 1的话是墙 不能走
			val , ok := next.at(maze)
			if !ok || val == 1 {
				continue
			}
			//看看你的地图 是否这个点 在你的地图里 已近走过了
			val,ok = next.at(steps)
			//如果这个点 已经走过了 也去除
			if !ok || val != 0 {
				continue
			}
			//如果这个点 是原点 也不能再走 原点也是走过的点 特殊的是原点是0  上面 判断条件是 排除0 的点 所以需要单独判断
			if next == start {
				continue
			}
			//出发点的坐标
			curwSteps ,_:=cur.at(steps)
			//在你的地图上 跟新这个找到的点 索引为上一个点+1
			steps[next.x][next.y] = curwSteps + 1
			//将这个点加入队列
			Q = append(Q,next)
		}
	}
	return steps
}

下面是main 测试函数

func main(){
	maze := readMaze("maze/maze.in")
	steps := walk(maze,point{0,0},point{len(maze)-1,len(maze[0])-1})
	for _,row :=range steps {
		for _, val := range row {
			fmt.Printf("%3d ", val)
		}
		fmt.Println()
	}
}

最后结果:

0 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 1 1 0 0 1
1 1 0 0 1 0
1 1 1 0 1 1