幅優先探索（BFS）は、始点から順に隣接ノードを訪問し、各レベルのノードをすべて処理してから次の深さへ進むアルゴリズムです。この手法は、グリッド上の連結領域の数え上げや迷路における最短ステップ数の算出に適しています。

1のブロック数をカウントする例

#include <iostream>
#include <queue>
using namespace std;

const int SIZE = 100;
int rows, cols;
int grid[SIZE][SIZE];
bool visited[SIZE][SIZE] = {false};

struct Point {
    int r, c;
};

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

bool isValid(int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (visited[r][c] || grid[r][c] == 0) return false;
    return true;
}

void exploreRegion(int startR, int startC) {
    queue<Point> q;
    q.push({startR, startC});
    visited[startR][startC] = true;

    while (!q.empty()) {
        Point cur = q.front();
        q.pop();

        for (int d = 0; d < 4; ++d) {
            int nr = cur.r + dr[d];
            int nc = cur.c + dc[d];
            if (isValid(nr, nc)) {
                q.push({nr, nc});
                visited[nr][nc] = true;
            }
        }
    }
}

int main() {
    cin >> rows >> cols;
    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
            cin >> grid[i][j];

    int regions = 0;
    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
            if (!visited[i][j] && grid[i][j] == 1) {
                regions++;
                exploreRegion(i, j);
            }

    cout << regions << endl;
    return 0;
}

迷路の最短ステップ計算

#include <iostream>
#include <queue>
using namespace std;

const int MAX_GRID = 100;
int H, W;
char maze[MAX_GRID][MAX_GRID];
bool seen[MAX_GRID][MAX_GRID] = {false};

struct State {
    int row, col, moves;
};

int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

bool canMove(int r, int c) {
    if (r < 0 || r >= H || c < 0 || c >= W) return false;
    if (seen[r][c] || maze[r][c] == '*') return false;
    return true;
}

int findShortestPath(State start, State goal) {
    queue<State> q;
    q.push(start);
    seen[start.row][start.col] = true;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        if (current.row == goal.row && current.col == goal.col)
            return current.moves;

        for (int dir = 0; dir < 4; ++dir) {
            int ny = current.row + dy[dir];
            int nx = current.col + dx[dir];
            if (canMove(ny, nx)) {
                q.push({ny, nx, current.moves + 1});
                seen[ny][nx] = true;
            }
        }
    }
    return -1;
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j)
            maze[i][j] = getchar();
        getchar(); // 改行を消費
    }

    State begin, end;
    cin >> begin.row >> begin.col >> end.row >> end.col;
    begin.moves = 0;

    cout << findShortestPath(begin, end) << endl;
    return 0;
}