CSP-J 入门级 · CSP 2022 入门级第一轮 第 20 题

（2）（洪水填充）

现有用字符标记像素颜色的 $8\times 8$ 图像。颜色填充的操作描述如下：给定起始像素的位置待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

试补全程序。

#include<bits/stdc++.h>
using namespace std;

const int ROWS = 8;
const int COLS = 8;

struct Point {
    int r, c;
    Point(int r, int c): r(r), c(c) {}
};

bool is_valid(char image[ROWS][COLS], Point pt,
              int prev_color, int new_color) {
    int r = pt.r;
    int c = pt.c;
    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
            ① && image[r][c] != new_color);
}

void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;
    queue.push(cur);

    int prev_color = image[cur.r][cur.c];
    ②;

    while (!queue.empty()) {
        Point pt = queue.front ();
        queue.pop ();

        Point points[4] = {③, Point(pt.r - 1, pt.c),
                           Point(pt.r

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

洪水填充是BFS的经典应用，核心在于理解“连通且同色”的定义。拿到题先别急着填空，盯着is_valid函数里的条件：边界、颜色是否等于起始色、是否已是新色。这三点缺一不可，尤其是防止重复入队导致死循环，这是命题人最爱挖的坑。

最容易在is_valid里把颜色判断写反，写成!=prev_color，那样连起始点自己都过不去，队列瞬间空，程序直接结束，选A的同学基本都能避开，但选B的会全军覆没。另外，很多人忘了在循环里对每个邻居都要检查is_valid，以为只要起点颜色对就行，结果把不同颜色的点也染了，逻辑完全跑偏。还有就是在染色顺序上，有人习惯先染色再入队，有人先入队再染色，其实BFS里为了防重复入队，必须是“先染色标记，再入队”，否则同一个点会被反复处理，队列爆炸，这也是为什么②必须填B而不是其他选项。

这道题考的是洪水填充算法，属于BFS（广度优先搜索）在二维网格上的具体应用。命题人想让你掌握的不仅是队列的使用，更是对“连通区域”和“状态标记”的理解。洪水填充的本质是：从起点出发，把所有与起点颜色相同、且在上下左右四个方向上可达的像素，全部替换成新颜色。关键在于“可达”的定义——路径上所有点颜色必须一致，且不能已经变成新颜色，否则就是重复处理。因此is_valid函数的三个条件缺一不可：边界检查、颜色等于起始色、不等于新色。这三个条件在代码里对应①，选A（image[r][c] == prev_color）才能正确筛选出待填充的像素。如果写成!=prev_color，起点自己都过不去，整个算法直接崩盘，这也是很多初学者容易踩的坑。接下来看②，程序里先记录prev_color，然后立刻把起点染成新色，这是为了防止起点被重复入队。BFS的标准套路是“先标记再入队”，否则同一个点会被多次加入队列，导致无限循环或超时。所以②必须填B（image[cur.r][cur.c] = new_color），其他选项要么改了错的位置，要么改了错的颜色，都会让后续逻辑全乱。再看③，这里需要列出四个方向的邻居。代码里已经写了上、右、左三个，唯独缺了下方向。根据坐标变化规律，下就是r+1，所以③填C（Point(pt.r+1, pt.c)）。很多人会误以为要写r-1，但r-1已经在数组里了，重复写反而多余。最后两个空④和⑤，在遍历邻居时，如果is_valid返回真，说明这个点确实需要填充。这时候必须先把它染成新色（④填D：image[p.r][p.c] = new_color），然后再入队（⑤填A：queue.push(p)）。顺序不能颠倒，因为入队后如果还没染色，下次再遇到这个点时is_valid会误判为“颜色不同”，导致漏填。整个流程下来，BFS保证了每个点只被访问一次，时间复杂度O(ROWS×COLS)，空间复杂度也是O(ROWS×COLS)，完全符合题目要求。从考频来看，二维数组与BFS在近年竞赛中非常活跃，尤其是洪水填充这类经典题型，几乎年年都有变种出现，比如改变边界条件、增加障碍物、或者要求统计填充面积等。命题人喜欢在细节处挖坑，比如is_valid里的颜色判断、染色顺序、方向数组的完整性，这些都是学生最容易忽略的地方。如果你能熟练掌握这类题的解题思路，不仅对当前题目有帮助，对后续遇到的类似网格遍历问题也能举一反三。总的来说，这道题的核心就是BFS + 状态标记，只要抓住“先染色再入队”和“is_valid三条件”这两点，就能稳稳拿下。