Day 21 · BFS 进阶 + 第二/三周复盘

题意：n × n 的 0/1 迷宫，只能走到相邻的、数字与自己不同的格子。给 m 次询问，每次问从某格出发能到达多少格（含自身）。

思路

「能互相到达」把格子分成若干连通块，同块内所有格子的答案都相等，等于块的大小。所以：

1. 一次全图扫描，用 BFS 给每个格子染色（id[i][j]），同时统计每块大小（cnt[块号]）。
2. 每次询问直接输出 cnt[id[i][j]]，O(1)。

总复杂度 O(n² + m)，实测 n = 1000、m = 10⁵ 时约 0.2 秒（详见下面的实测结果）。

2 2
01
10
1 1
2 2

4
4

2×2 的棋盘上 0 和 1 交错，四格两两可达，所以从哪一格出发都能到 4 格。

完整代码

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

int n, m;
char g[1005][1005];      // 迷宫（0/1 字符）
int id[1005][1005];      // 每个格子属于哪个连通块，0 表示还没染色
int cnt[1000005];        // 每个连通块的大小（能走到的格子数）
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%s", g[i]);

    int blocks = 0;                 // 连通块编号，从 1 开始（0 留给"未访问"）
    queue<int> q;                   // 队列里存 i*n+j，省内存
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(id[i][j]) continue;              // 已经染过色，跳过
            blocks++;
            id[i][j] = blocks;
            q.push(i * n + j);
            int total = 0;
            while(!q.empty()){
                int cur = q.front(); q.pop();
                int x = cur / n, y = cur % n;
                total++;
                for(int d = 0; d < 4; d++){
                    int nx = x + dx[d], ny = y + dy[d];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if(id[nx][ny]) continue;                // 已经属于某个连通块
                    if(g[nx][ny] == g[x][y]) continue;      // ★ 数字相同不能走
                    id[nx][ny] = blocks;                    // 染成同一块
                    q.push(nx * n + ny);
                }
            }
            cnt[blocks] = total;        // 这块的答案就是 total
        }
    }

    // 询问直接查表，O(1) 一个
    for(int k = 0; k < m; k++){
        int i, j;
        scanf("%d %d", &i, &j);
        printf("%d\n", cnt[id[i - 1][j - 1]]);
    }
    return 0;
}

易错点

• 每个询问都单独 BFS → 10¹¹ 次操作，必 TLE。这是本题唯一的门槛。
• 转移条件写错：是「两格数字不同才能走」，写成「必须是 1」或「必须是 0」就错了。
• 用 0 号连通块：id 初值 0 用来表示「没访问过」，所以块编号必须从 1 开始。
• 询问坐标忘减 1：题目行列从 1 开始，数组从 0 开始，要写 id[i-1][j-1]。
• 不用 cin/cout 加同步：n = 10⁶ 级别输入 + 10⁵ 输出，建议直接用 scanf/printf，或者开头加 ios::sync_with_stdio(false);。

题意：n 行 m 列的军团方阵，有 a 个感染源，瘟疫每小时向上下左右扩散一格。给 b 个领主的位置，按输入顺序输出每个人被感染的时刻（在感染源上的人时刻为 0）。

思路

多源 BFS：把 a 个感染源全部以距离 0 入队，然后照常 BFS。搜完后 dist[x][y] 就是「到最近感染源的时间」，也就是领主被感染的时刻。

为什么对？因为它们等价于从一个「超级源点」出发的普通 BFS（见第 2 节）。

5 4 2 3
1 1
5 4
3 3
5 3
2 4

3
1
3

感染源在 (1,1) 和 (5,4)。
(3,3)：从 (5,4) 走 |3−5|+|3−4| = 3 步，从 (1,1) 要 4 步 → 取 3。
(5,3)：紧挨着 (5,4) → 1 步。
(2,4)：从 (5,4) 走 3 步，从 (1,1) 走 4 步 → 3。

完整代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int n, m, a, b;
int dist[505][505];                 // -1 表示还没被感染（没访问）
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main(){
    scanf("%d %d %d %d", &n, &m, &a, &b);
    memset(dist, -1, sizeof(dist));

    queue<int> q;
    // ★ 多源 BFS：所有感染源一起入队，距离都是 0
    for(int k = 0; k < a; k++){
        int x, y;
        scanf("%d %d", &x, &y);
        if(dist[x][y] == -1){       // 同一格重复出现也只用入队一次
            dist[x][y] = 0;
            q.push(x * (m + 1) + y);
        }
    }

    while(!q.empty()){
        int cur = q.front(); q.pop();
        int x = cur / (m + 1), y = cur % (m + 1);
        for(int d = 0; d < 4; d++){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if(dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push(nx * (m + 1) + ny);
        }
    }

    // 输出顺序和输入顺序一致，所以读完一个就输出一个
    for(int k = 0; k < b; k++){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", dist[x][y]);
    }
    return 0;
}

易错点

• 对每个领主单独 BFS：b ≤ 10⁵，直接爆炸。多源 BFS 只需要搜一遍。
• 感染源重复入队：a 可能远大于格子数，加 if(dist[x][y] == -1) 去重。
• 输出顺序：题目要求「与输入顺序一致」，所以不能排序、不能存起来乱输。
• 坐标从 1 开始：数组按 1..n、1..m 使用，memset(dist, -1, ...) 把整个数组设为 −1 正好当哨兵。
• 编码坐标时用的是 x * (m + 1) + y，别写成 x * m + y（列下标是 1..m，用 m 做基数会撞车）。

题意：贝茜在 (0,0)。M 颗流星分别在时刻 Tᵢ 砸在 (Xᵢ, Yᵢ)，把落点和上下左右四格烧成焦土。她每秒走一格，只能待在 X, Y ≥ 0 的区域，问最少多久能走到一个永远安全的格子（安全 = 永远不会被烧）；到不了输出 −1。

思路

1. 预处理：burn[x][y] = 该格最早被烧的时刻（没被烧记成 INF）。对每颗流星更新落点 + 四邻，取 min。
2. BFS：从 (0,0) 出发，进入 (nx,ny) 的条件是 dist[x][y] + 1 < burn[nx][ny]。
3. 每弹出一个格子，如果它的 burn 是 INF，说明站在安全格上，而 BFS 保证这是最早时刻 → 输出 dist 并结束。
4. 队列空还没找到 → 输出 −1。另外起点若在时刻 0 就被砸，直接 −1。

4
0 0 2
2 1 2
1 1 2
0 3 5

5

时刻 2 被烧：(0,0)、(1,0)、(0,1)、(2,0)、(1,1)、(2,1)、(3,1)、(2,2)、(1,2)。
时刻 5 被烧：(0,3)、(1,3)、(0,2)、(0,4)。
贝茜的路线：(0,0) → (0,1) → (0,2) → (0,3) → (0,4) → (1,4)，第 5 秒站上 (1,4)，它永远不会被烧。

完整代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int N = 305;                  // 流星坐标 0..300，烧焦还会波及 301，多开一点
const int INF = 0x3f3f3f3f;

int burn[N][N];                     // burn[x][y] = 最早被烧的时刻，INF = 永远安全
int dist[N][N];                     // 贝茜到达的时刻，-1 表示没到过
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main(){
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            burn[i][j] = INF;
    memset(dist, -1, sizeof(dist));

    int M;
    scanf("%d", &M);
    for(int k = 0; k < M; k++){
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        // ★ 流星把落点和上下左右四格都变成焦土，取「最早被烧」的时刻
        if(t < burn[x][y]) burn[x][y] = t;
        for(int d = 0; d < 4; d++){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(t < burn[nx][ny]) burn[nx][ny] = t;
        }
    }

    if(burn[0][0] == 0){            // 时刻 0 起点就被砸，活不下来
        printf("-1\n");
        return 0;
    }

    queue<int> q;
    dist[0][0] = 0;
    q.push(0);
    while(!q.empty()){
        int cur = q.front(); q.pop();
        int x = cur / N, y = cur % N;
        if(burn[x][y] == INF){      // 站在永远不会被烧的格子上，安全！
            printf("%d\n", dist[x][y]);
            return 0;
        }
        for(int d = 0; d < 4; d++){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(dist[nx][ny] != -1) continue;
            // ★ 必须「严格早于」被烧的时刻才能踏进去
            if(dist[x][y] + 1 < burn[nx][ny]){
                dist[nx][ny] = dist[x][y] + 1;
                q.push(nx * N + ny);
            }
        }
    }
    printf("-1\n");
    return 0;
}

易错点

• 把 < 写成 <=：题目规定「时刻 t 被烧的格子，只能在 t 之前出现」，所以取等号是错的。
• 数组只开到 301：烧焦会波及坐标 301，必须留出空间（开 305）。
• 忘记处理起点：burn[0][0] == 0 时要直接输出 −1，否则会输出 0（错误答案）。
• 把时间当成状态：(x, y, t) 状态数会膨胀到 9×10⁷，既费内存又没必要。
• 忘了 burn 要取 min：同一格可能被多颗流星波及，写 burn[x][y] = t 会被后面的流星覆盖成较晚的时刻，导致答案错误。

题意：2ᵏ × 2ᵏ 的棋盘，公主占一格不能铺。用 L 形毯子（3 格，4 种朝向）把其余格子铺满，每格只铺一层。输出任意一种方案。

思路

把棋盘切成四个象限。公主在其中一块里，我们在正中放一块毯子盖住另外三块各 1 格，于是四块都变成「有一个洞」的同类子问题，规模减半，递归求解。

递归到边长 1 就结束。核心是那句「洞在哪个象限」的分支判断。

3
3 3

5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1

8 × 8 的棋盘去掉公主那一格，还剩 63 格，63 ÷ 3 = 21 —— 正好 21 块毯子，也正好是 21 行输出。

完整代码

#include <cstdio>

int k, px, py;

// 用一个 L 形毯子盖住「洞」以外的三个中心格
// (x,y) 当前方块左上角；len 边长；(hx,hy) 洞的位置
void solve(int x, int y, int len, int hx, int hy){
    if(len == 1) return;                    // 1×1 不用盖
    int half = len >> 1;
    int cx = x + half, cy = y + half;       // 中心 2×2 块的右下角

    if(hx < cx && hy < cy){                 // 洞在左上象限
        printf("%d %d 1\n", cx, cy);        // 盖住右上、左下、右下三个中心格
        solve(x,  y,  half, hx,     hy);        // 左上：洞不变
        solve(x,  cy, half, cx - 1, cy);        // 右上：洞 = 自己的中心格
        solve(cx, y,  half, cx,     cy - 1);    // 左下
        solve(cx, cy, half, cx,     cy);        // 右下
    } else if(hx < cx && hy >= cy){         // 洞在右上象限
        printf("%d %d 2\n", cx, cy - 1);
        solve(x,  y,  half, cx - 1, cy - 1);
        solve(x,  cy, half, hx,     hy);        // 右上：洞不变
        solve(cx, y,  half, cx,     cy - 1);
        solve(cx, cy, half, cx,     cy);
    } else if(hx >= cx && hy < cy){         // 洞在左下象限
        printf("%d %d 3\n", cx - 1, cy);
        solve(x,  y,  half, cx - 1, cy - 1);
        solve(x,  cy, half, cx - 1, cy);
        solve(cx, y,  half, hx,     hy);        // 左下：洞不变
        solve(cx, cy, half, cx,     cy);
    } else {                                // 洞在右下象限
        printf("%d %d 4\n", cx - 1, cy - 1);
        solve(x,  y,  half, cx - 1, cy - 1);
        solve(x,  cy, half, cx - 1, cy);
        solve(cx, y,  half, cx,     cy - 1);
        solve(cx, cy, half, hx,     hy);        // 右下：洞不变
    }
}

int main(){
    scanf("%d %d %d", &k, &px, &py);
    int n = 1 << k;                         // 2^k
    solve(1, 1, n, px, py);
    return 0;
}

易错点

• 递归时把洞的位置搞混：只有「洞所在的那个象限」保持洞不变，另外三个象限的洞是它们靠近中心的那一格。这四行 solve 的参数是最容易写错的地方，写完拿样例对一遍。
• 输出用 cout << endl：35 万行输出，endl 每次都强制刷缓冲，会明显变慢。用 printf("\n") 或 '\n'。
• 递归终止写成 len == 0：应该是 len == 1（只剩洞那一格，没得盖）。
• 坐标从 1 开始：递归入口是 solve(1, 1, 2^k, px, py)，减半时用 len >> 1，别写成除以 2 后又少算一格。
• 这题不需要开二维数组存棋盘，只要按「象限 → 中心三格」的规律直接输出坐标就行了。