P1141 01迷宫

calendar May 8, 2026 · 2 分钟阅读 · 广度优先搜索 图论 Flood Fill  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1141
难度 普及
知识点 BFS、Flood Fill、图的连通块、记忆化查询

题目描述

给定一个 N × N 的 01 迷宫（每个格子为 0 或 1）。从某格子出发，每次可以移动到上下左右四个方向中与当前格子数字不同的格子。求从若干个查询位置出发，能够到达的格子总数（即连通块大小）。

  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 10⁵（查询次数很多）

解题思路

核心思想：Flood Fill + 记忆化

本题的本质是：所有相同数字相邻的格子属于同一个区域，但只允许跨数字移动。换句话说，从任意格子出发，只能经过一条"数字交替"的路径到达其他格子——这形成一个连通块。

1. BFS 扩展连通块

使用 BFS 从起点出发，将所有与起点"数字交替连通"的格子全部找出来，并用 book[][] 记录该连通块中每个格子属于哪个答案。

当前位置 map[x][y]，可以走向 tx,ty 的条件：
  - 在边界内
  - 未被当前 BFS 访问过（book[tx][ty] == 0）
  - map[x][y] != map[tx][ty]  ← 关键：必须数字不同

2. 记忆化：避免重复搜索

题目有高达 10⁵ 次查询，直接对每次查询都 BFS 会严重超时。

观察到：同一个连通块内的所有格子，答案相同。因此当 BFS 完成后，把 book 中该连通块所有格子都标记为同一个答案值 ans。后续查询到已标记的格子时，直接输出即可，无需重新 BFS。

完整代码

C++

#include <iostream>
using namespace std;

char map[1001][1001];
int n, m, sx, sy, book[1001][1001], dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

struct Node {
    int x, y;
} que[1000001];

void bfs(int x, int y) {
    int ans = 1, head = 0, tail = 1;
    que[head].x = x;
    que[head].y = y;
    book[x][y] = 1;

    while (head < tail) {
        for (int k = 0; k < 4; ++k) {
            int tx = que[head].x + dir[k][0];
            int ty = que[head].y + dir[k][1];
            if (tx < 1 || ty < 1 || tx > n || ty > n
                || book[tx][ty] != 0
                || map[que[head].x][que[head].y] == map[tx][ty]) continue;
            que[tail].x = tx;
            que[tail++].y = ty;
            book[tx][ty] = 1;
            ++ans;
        }
        ++head;
    }

    for (int j = 0; j < tail; ++j)
        book[que[j].x][que[j].y] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> map[i][j];

    for (int i = 0; i < m; ++i) {
        cin >> sx >> sy;
        if (book[sx][sy] != 0) cout << book[sx][sy] << '\n';
        else {
            bfs(sx, sy);
            cout << book[sx][sy] << '\n';
        }
    }

    return 0;
}

关键代码讲解

1. BFS 扩展

// 关键条件：必须走向"数字不同"的格子
if (map[que[head].x][que[head].y] == map[tx][ty]) continue;

这是01迷宫的核心约束——只能跨数字移动。

2. 入队与计数

que[tail].x = tx;
que[tail++].y = ty;  // 先写入，再 ++tail
book[tx][ty] = 1;
++ans;

每扩展一个合法邻居就入队、book 标记、ans++，起点在 BFS 开始前 ans = 1，两者合计即为连通块大小。

3. 批量回填答案

for (int j = 0; j <= tail; ++j)
    book[que[j].x][que[j].y] = ans;

BFS 结束后，整个连通块所有格子的 book 值都设为同一个 ans，后续查询直接命中缓存。

复杂度分析

方法 时间复杂度 空间复杂度
整体（含 M 次查询） 最坏 O(N² + M)，每个格子最多被 BFS 访问一次 O(N²)（book 数组 + 队列）
  • 无记忆化：每次查询 BFS 最坏 O(N²)，M 次共 O(M · N²) → 无法承受
  • 有记忆化：每个格子只 BFS 一次，后 O(1) 查表 → O(N² + M)

易错点

  1. “数字相同不能走”：map[que[head].x][que[head].y] == map[tx][ty] 时必须 continue，而非相等才能走。
  2. tail 初始化为 1：tail = 1 表示起点已占索引 0，队列初始非空；tail = 0 会导致 BFS 根本不执行。
  3. head < tail 循环条件：tail 指向"下一个可写位置"，head == tail 时队列空，必须严格小于。

其他语言解法

TODO