宽度优先搜索（BFS）总结

基本思想

宽度优先搜索一般用队列（queue）实现，且总是按层次的顺序进行遍历。解这类题的一般套路：

1. 定义一个结构体作为节点来存储信息（如保存横纵坐标x、y），后续队列以该结构体为单位来存储。
2. 定义bool型数组，标记每个位置是否入过队列。
3. 定义增量数组表示若干个方向（四个、六个或八个）。
4. 定义返回值为bool类型的检查函数，判断当前节点是否越界或入过队列或不满足题目条件。
5. 编写宽搜函数bfs()，其中定义一个队列，将初始节点入队并标记已访问。当队列不为空一直循环，循环体中先访问队头元素并出队，检查其若干个方向上的节点是否满足条件，满足则入队并标记，继续循环。

代码模板

典型例题

输入：

5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2

输出：

11

题解

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

//记录每个节点的信息
struct node {
    int x;
    int y;
    int step;
} Node, T;

int n, m;
char map[100][100];
bool hasIn[100][100] = {false};		//标记是否已入过队列

//增量数组 四个方向 上下左右
int X[] = {0, 0, -1, 1};
int Y[] = {1, -1, 0, 0};

//判断是否越界或已入过队列
bool check(int x, int y)
{
    if(x < 0 || y < 0 || x >= m || y >= n)
        return false;
    if(map[x][y] == '*' || hasIn[x][y] == true)
        return false;
    return true;
}

int bfs(int x, int y)
{
    queue<node> q;
    //先将当前起始位置入队
    Node.x = x;
    Node.y = y;
    Node.step = 0;
    q.push(Node);
    hasIn[x][y] = true;
    //当队列不为空则一直循环
    while(!q.empty())
    {
    	//访问队首元素并出队
        node top = q.front();
        q.pop();
        //入过到终点则返回 必然是最少步数
        if(map[top.x][top.y] == 'T')        //top.x == T.x && top.y == T.y
            return top.step;
        //遍历四个方向
        for (int i = 0; i < 4; i ++ )
        {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            //满足条件则入队
            if(check(newX, newY))
            {
                Node.x = newX;
                Node.y = newY;
                Node.step = top.step + 1;
                q.push(Node);
                hasIn[newX][newY] = true;		//标记
            }
        }
            
    }
    
    return -1;
}

int main()
{
    int x, y;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        getchar();			//过滤换行符
        for (int j = 0; j < m; j ++ )
        {
        	//map[i][j] = getchar();
            scanf("%c", &map[i][j]);              //[segmentation fault] scanf字符要加&
        }
        map[i][m + 1] = '\0';
    }
    
    scanf("%d%d", &x, &y);
    printf("%d\n", bfs(x, y));
    return 0;
}

总结

bfs主要就是应用一个队列和增量数组，将队列中队头元素能到达的每一个节点依次进行遍历，满足条件则入队，直到队空为止。此类思想适合解决迷宫、地图类问题，就是优先遍历当前节点能直接到达的节点。具体问题还需在模板上做特定修改，要灵活运用。

此类题目汇总（持续更新）

1. 【蓝桥杯java】迷宫（BFS）
2. PAT A1091 Acute Stroke(三维数组BFS)
   …