广度优先搜索

广度优先搜索（BFS）一般由队列实现，且总是按层次的顺序进行遍历。模板如下：

void bfs(int s) {
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        取出队首元素top;
        访问队首元素top;
        将队首元素出队;
        将top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
    }
}

例1

分析：枚举每一个位置的元素，如果为0，则跳过；如果为1，则用bfs查询与该位置相邻的4个位置（前提不出界），判断它们是否为1（如果某个相邻位置为1，则同样查询与该位置相邻的4个位置，直到整个“1”块访问完毕）。为了防止走回头路，设置一个inq数组记录每个位置是否在bfs中入过队。

#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 100;
struct Node {
    int x, y;
} node;

int n, m;//矩阵大小n*m
int matrix[maxn][maxn];
bool inq[maxn][maxn];
//(x[0],y[0])代表向上，(x[1],y[1])代表向下，（x[2],y[2]）代表向右，（x[3],y[3]）代表向左
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};

//判断（x，y）是否需要访问
bool judge(int x, int y) {
    if (x >= n || x < 0 || y >= m || y < 0) {
        return false;
    }
    if (matrix[x][y] == 0 || inq[x][y] == true) {
        return false;
    }
    return true;
}

void bfs(int x, int y) {
    queue<Node> q;
    node.x = x;
    node.y = y;
    q.push(node);
    inq[x][y] = true;
    while (!q.empty()) {
        Node top = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if (judge(newX, newY) == true) {
                node.x = newX;
                node.y = newY;
                q.push(node);
                inq[newX][newY] = true;
            }
        }
    }
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1 && inq[i][j] == false) {
                res++;
                bfs(i, j);//将该块所有的1都标记为已入队
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

例2

分析：从起点S开始计数遍历的层数，到达终点T时的层数就是最少步数。

#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 100;
struct Node {
    int x, y;
    int step;
} S, T, temp;

int n, m;
char maze[maxn][maxn];//迷宫信息
bool inq[maxn][maxn];
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};

bool judge(int x, int y) {
    if (x >= n || x < 0 || y >= m || y < 0) {
        return false;
    }
    if (maze[x][y] == '*') {
        return false;
    }
    if (inq[x][y] == true) {
        return false;
    }
    return true;
}

int bfs() {
    queue<Node> q;
    q.push(S);
    while (!q.empty()) {
        Node top = q.front();
        q.pop();
        if (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 (judge(newX, newY) == true) {
                temp.x = newX;
                temp.y = newY;
                temp.step = top.step + 1;
                q.push(temp);
                inq[newX][newY] = true;
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();//接收换行符
        for (int j = 0; j < m; j++) {
            maze[i][j] = getchar();
        }
        maze[i][m + 1] = '\0';
    }
    scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);
    S.step = 0;
    printf("%d\n", bfs());
    return 0;
}

1091 Acute Stroke