> For the complete documentation index, see [llms.txt](https://dingyj.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dingyj.gitbook.io/blog/golang/basic/go-yu-yan-pa-chong/go-yu-yan-pa-chong-guang-du-you-xian-suan-fa.md).

# Go语言爬虫 - 广度优先算法

练习爬虫之前，先练习用广度优先算法走迷宫。

![](/files/-LhuA0GPUGVmUTyS3kBM)

广度优先算法的走法如果无视墙壁和范围，可以理解成下面的这张图：

![](/files/-LhxEjBExTaUVJADoBtT)

 加上范围和墙壁的识别，把需要探索的内容不断添加到一个二维的队列中。

![](/files/-LhxEyhjHW7Wgi5nph16)

实现代码如下：

```go
package main

import (
	"fmt"
	"os"
)

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)

	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
}

// 定义探索方向
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}
}

func (p point) at(grid [][]int) (int, bool) {
	if p.i < 0 || p.i >= len(grid) {
		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(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:]

		if cur == end {
			break
		}
		// 根据探索方向进行探索
		for _, dir := range dirs {
			// 根据方向计算需要为point定义方法add
			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是一个Int
			curSteps, _ := cur.at(steps)
			// 下一步可以探索坐标的值设置为+1
			steps[next.i][next.j] =
				curSteps + 1
			// 传入队列
			Q = append(Q, next)
		}
	}

	return steps
}

func main() {
	maze := readMaze("./maze.in")

	steps := walk(maze, point{0, 0},
		point{len(maze) - 1, len(maze[0]) - 1})

	for _, row := range steps {
		for _, val := range row {
			// %3表示3位对齐
			fmt.Printf("%3d", val)
		}
		fmt.Println()
	}

	// TODO: construct path from steps
}

```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dingyj.gitbook.io/blog/golang/basic/go-yu-yan-pa-chong/go-yu-yan-pa-chong-guang-du-you-xian-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.