「Flood-it!」涂满它！

形式化题目

给定一个 $N \times N$ 的网格（ $2 \leqslant N \leqslant 8$ ），每个格子有一种颜色，颜色是 $0 \sim 5$ 中的整数。定义两个格子连通，当且仅当它们有公共边且颜色相同。

每一步操作：选定一种颜色 $c$ ，把所有与左上角连通的格子（包括左上角本身）都改成颜色 $c$ 。

求最少多少步操作后，所有格子的颜色相同。

多组数据（不超过 20 组）， $N = 0$ 表示输入结束。

样例解释：第一个样例 $2\times 2$ 全是颜色 0，天然同色，答案 0；第二个样例 $3\times 3$ 如下（* 表示当前与左上角连通的区域，初始只有左上角自己）：

初始	选颜色 1 后	选颜色 2 后	选颜色 1 后
`*12`	`**2`	`***`	`***`
`112`	`**2`	`***`	`***`
`221`	`221`	`**1`	`***`

第一步把左上角染成 1，吞并了左列和上中的两个 1；第二步染成 2，吞并右边一列的 2；第三步染成 1，吞并剩下的 1。三步是最少的，所以答案为 3。

暴力解法

思路

把游戏过程看成一个最短路问题：状态是当前"与左上角连通的格子集合" $S$ ，每个状态有 6 条出边（选 6 种颜色），从初始状态 $S_0$ 出发做 BFS，第一次到达"覆盖全图"的状态时的层数就是答案。

这里有一个关键的抽象：连通块内部的颜色不重要。因为无论连通块是什么颜色，下一步能吞并谁都只取决于 $S$ 的形状和 $S$ 外部邻居的颜色；染色时整个连通块会被统一改成新颜色。所以状态可以只用格子集合表示， $N \leqslant 8$ 时一个 64 位整数就能编码。

但这个朴素 BFS 走不远： $S$ 的可能形态是"包含左上角的任意连通格集"，数量随 $N$ 指数级增长；搜索深度可达 15 步以上，每层 6 个分支，BFS 需要把整层状态都存进队列，内存和时间同时爆炸。

代码

复杂度

状态数为指数级，深度 $d$ 时内存 $O(6^d)$ ，在 $N = 8$ 、答案可达 16 的数据下不可行。

瓶颈

内存瓶颈：BFS 必须存储整层状态，状态总量指数级。
无效搜索：大量分支明显不可能在剩余步数内完成，朴素 BFS/DFS 对此毫无察觉。

正解

思路

两个瓶颈分别指向两个经典武器：迭代加深搜索（IDDFS） 把内存从"存整层"降到"存一条 DFS 路径"；A* 估价剪枝 排掉明显无望的分支。两者结合就是 IDA*。

第一步：找一个可采纳的估价函数。 注意每一步操作后，新并入连通块的格子颜色全部相同（都等于所选颜色）。因此每一步至多把棋盘上"尚未被吞并的某种颜色"全部消灭掉一种——反过来说，如果棋盘上还有 $k$ 种颜色出现在连通块之外，那么至少还需要 $k$ 步。于是定义

h(S) = \text{集合 } S \text{ 之外出现的颜色种数}

它永远不会高估真实剩余步数（可采纳性），这正是 IDA* 需要的估价函数。

第二步：IDA 框架。* 最优解不会小于 $h(S_0)$ ，所以从 depth = h(S_0) 开始，每轮做深度受限 DFS：若当前 $h(S) > left$ （剩余允许步数）直接回退；left 耗尽还没覆盖全图就回退。某轮成功时的 depth 就是最少步数；失败则 depth += 1 再来。迭代加深保证了第一个被找到的可行深度就是最优深度。

第三步：两个工程优化。

同层去重：同一状态下选不同颜色可能得到相同的 $S$ （例如两种颜色都只能吞到同一批格子），把后继放进集合去重，避免同一子树被搜多遍。
分支排序：按 $h(S‘)$ 从小到大尝试后继，优先走向"剩余颜色更少"的局面，让最优解尽早出现、剪枝尽早生效。

flowchart LR
    A["depth = h(S0)"] --> B["深度受限 DFS"]
    B --> C{"h(S) > left ?"}
    C -- 是 --> D["剪枝回退"]
    C -- 否 --> E["后继去重 + 按 h 排序"]
    E --> F{"找到全覆盖?"}
    F -- "本轮成功" --> G["输出 depth"]
    F -- "left 耗尽" --> H["depth += 1"]
    D --> H
    H --> B

实现要点：格子按 $r \cdot N + c$ 编号，状态用位掩码表示；转移时收集紧贴 $S$ 边界的所选颜色格子作种子，沿同色格 BFS 扩张；6 种颜色各存一个全量掩码，color_mask[c] & ~mask != 0 即可 $O(1)$ 判断颜色 $c$ 是否还没被吞完。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 15:53
# update_at: 2026-10-01 15:53

import sys

COLORS = range(6)      # 颜色编号 0..5
DR = (-1, 0, 1, 0)     # 上、右、下、左
DC = (0, 1, 0, -1)


def neighbors(idx: int, n: int) -> list[int]:
    """格子 idx（按 r*n+c 编号）的相邻格子编号列表。"""
    r, c = divmod(idx, n)
    return [(r + dr) * n + (c + dc)
            for dr, dc in zip(DR, DC)
            if 0 <= r + dr < n and 0 <= c + dc < n]


def start_mask(grid: list[int], nei: list[list[int]]) -> int:
    """初始时与左上角同色连通的区域（位掩码，第 i 位表示第 i 个格子）。"""
    seen = 1
    stack = [0]
    while stack:
        i = stack.pop()
        for j in nei[i]:
            if grid[j] == grid[0] and not seen >> j & 1:
                seen |= 1 << j
                stack.append(j)
    return seen


def expand(grid: list[int], nei: list[list[int]], mask: int, color: int) -> int:
    """区域染成 color 后能吞并的格子：相邻的 color 色格及其连通块。"""
    gained = 0
    # 种子：紧贴区域的 color 色格；再沿同色格 BFS 扩到整个连通块
    stack = [j for i in range(len(nei)) if mask >> i & 1
             for j in nei[i] if grid[j] == color and not mask >> j & 1]
    while stack:
        i = stack.pop()
        if gained >> i & 1:
            continue
        gained |= 1 << i
        stack += [j for j in nei[i]
                  if grid[j] == color and not (mask | gained) >> j & 1]
    return mask | gained


def remaining_colors(color_mask: list[int], mask: int) -> int:
    """还没被吞并的颜色种数：一步只能整块吞掉一种颜色，故它是剩余步数下界。"""
    return sum(cm & ~mask != 0 for cm in color_mask)


def dfs(grid: list[int], nei: list[list[int]], color_mask: list[int],
        full: int, mask: int, left: int) -> bool:
    """IDA* 深度受限搜索：能否再用 left 步吞满整个棋盘。"""
    if mask == full:
        return True
    if remaining_colors(color_mask, mask) > left:
        return False
    # 不同颜色可能吞出同一个局面，用集合去重；先试启发值小的分支，剪枝更早生效
    succ = sorted({expand(grid, nei, mask, c) for c in COLORS} - {mask},
                  key=lambda m: remaining_colors(color_mask, m))
    return any(dfs(grid, nei, color_mask, full, m, left - 1) for m in succ)


def solve_case(n: int, rows: list[list[int]]) -> int:
    """单个棋盘的最少步数：IDA* 从启发函数给出的下界开始逐步加深。"""
    grid = [v for row in rows for v in row]
    nei = [neighbors(i, n) for i in range(n * n)]
    full = (1 << (n * n)) - 1
    # color_mask[c]：颜色 c 的所有格子组成的位掩码
    color_mask = [sum(1 << i for i in range(n * n) if grid[i] == c)
                  for c in COLORS]
    mask = start_mask(grid, nei)
    if mask == full:
        return 0
    depth = remaining_colors(color_mask, mask)  # 最优解不会小于这个下界
    while not dfs(grid, nei, color_mask, full, mask, depth):
        depth += 1
    return depth


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    while (n := next(data)) != 0:
        rows: list[list[int]] = []
        for _ in range(n):
            rows.append([next(data) for _ in range(n)])
        out.append(str(solve_case(n, rows)))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:10
 * update_at: 2026-10-06 18:10
 */

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 8;          // 棋盘最大边长
const int MAXV = MAXN * MAXN; // 格子总数最大值

int n;                       // 当前棋盘边长
ll full;                     // 全 1 掩码，表示所有格子都被吞并
ll color_mask[6];            // color_mask[c] 表示颜色 c 的格子集合
int grid[MAXV];              // grid[i] 表示第 i 个格子的颜色
vector<int> adj[MAXV];       // 每个格子的四邻接格子

// 初始时与左上角同色的连通区域（广度优先）
ll start_mask() {
    ll mask = 1;
    int q[MAXV], head = 0, tail = 0;
    q[tail++] = 0;
    while (head < tail) {
        int u = q[head++];
        for (int v : adj[u]) {
            if (grid[v] == grid[0] && !(mask >> v & 1)) {
                mask |= 1LL << v;
                q[tail++] = v;
            }
        }
    }
    return mask;
}

// 把当前区域 mask 染成 color，返回新区域
ll expand(ll mask, int color) {
    int q[MAXV], head = 0, tail = 0;
    // 种子：紧贴区域且颜色为 color 的格子
    for (int u = 0; u < n * n; ++u) {
        if (!(mask >> u & 1)) continue;
        for (int v : adj[u]) {
            if (grid[v] == color && !(mask >> v & 1)) {
                q[tail++] = v;
            }
        }
    }
    ll gained = 0;
    while (head < tail) {
        int u = q[head++];
        if (gained >> u & 1) continue;
        gained |= 1LL << u;
        for (int v : adj[u]) {
            if (grid[v] == color && !(mask >> v & 1) && !(gained >> v & 1)) {
                q[tail++] = v;
            }
        }
    }
    return mask | gained;
}

// 剩余颜色种数，是完成所需步数的可采纳下界
int remaining_colors(ll mask) {
    int cnt = 0;
    for (int c = 0; c < 6; ++c) {
        if (color_mask[c] & ~mask) ++cnt;
    }
    return cnt;
}

// IDA* 深度受限搜索：能否在 left 步内吞满整个棋盘
bool dfs(ll mask, int left) {
    if (mask == full) return true;
    if (remaining_colors(mask) > left) return false;

    // 生成 6 种颜色转移，去重，按启发值从小到大尝试
    ll nxt[6];
    int nxt_cnt = 0;
    for (int c = 0; c < 6; ++c) {
        ll ns = expand(mask, c);
        if (ns == mask) continue; // 该颜色没有吞到新格子
        bool dup = false;
        for (int i = 0; i < nxt_cnt; ++i) {
            if (nxt[i] == ns) { dup = true; break; }
        }
        if (!dup) nxt[nxt_cnt++] = ns;
    }
    // 按剩余颜色数升序排序，优先尝试更优分支
    for (int i = 0; i < nxt_cnt; ++i) {
        for (int j = i + 1; j < nxt_cnt; ++j) {
            if (remaining_colors(nxt[i]) > remaining_colors(nxt[j])) {
                ll tmp = nxt[i]; nxt[i] = nxt[j]; nxt[j] = tmp;
            }
        }
    }
    for (int i = 0; i < nxt_cnt; ++i) {
        if (dfs(nxt[i], left - 1)) return true;
    }
    return false;
}

// 求解单个测试用例
int solve_case() {
    if (n == 0) return 0;
    for (int i = 0; i < n * n; ++i) adj[i].clear();
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            int u = r * n + c;
            if (r > 0) adj[u].push_back((r - 1) * n + c);
            if (r + 1 < n) adj[u].push_back((r + 1) * n + c);
            if (c > 0) adj[u].push_back(r * n + (c - 1));
            if (c + 1 < n) adj[u].push_back(r * n + (c + 1));
        }
    }
    for (int c = 0; c < 6; ++c) color_mask[c] = 0;
    for (int i = 0; i < n * n; ++i) {
        color_mask[grid[i]] |= 1LL << i;
    }
    full = (1LL << (n * n)) - 1;
    ll mask = start_mask();
    if (mask == full) return 0;
    int depth = remaining_colors(mask);
    while (!dfs(mask, depth)) ++depth;
    return depth;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n && n != 0) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) cin >> grid[i * n + j];
        }
        cout << solve_case() << "\n";
    }
    return 0;
}

复杂度

单次染色转移用 BFS 扩张， $O(N^2)$ ；估价函数 $O(6)$ 。IDA* 的最坏复杂度仍是指数级的（分支 6、深度 $\leqslant 16$ ），但估价剪枝 + 去重 + 排序让实际搜索树非常小， $N \leqslant 8$ 的数据跑得很快。DFS 只维护一条搜索路径，额外内存 $O(\text{depth})$ ，彻底消除 BFS 的内存瓶颈。

总结

核心抽象：连通块内部颜色不影响未来，状态 = 已吞并格子集合，可用 64 位位掩码编码。
下界：每步至多消灭一种剩余颜色，故 $h(S)$ = 剩余颜色种数是可采纳估价函数。
算法：IDA* 迭代加深，估价剪枝，后继去重 + 按 $h$ 排序；深度从 $h(S_0)$ 起递增，首个可行深度即答案。
朴素 BFS 的内存瓶颈由迭代加深消除，无效搜索由估价函数消除——这是"从暴力到正解"的完整推导链。

图示解析

搜索空间的剪枝效果

以样例 2 的 $3\times 3$ 棋盘为例， $S_0$ 只含左上角， $S$ 外出现颜色 $\{1, 2\}$ ，所以 $h(S_0) = 2$ ，IDA* 从 depth = 2 开始：

depth = 2：任何第一步染色后 $h$ 至多是 1，若两步真能完成需要每步恰好消灭一种颜色；实际试遍所有分支（去重后）都失败——例如先染 2 只能吞到 *22 / 112 / 221 的右上角，剩两个 1 不相连无法一步消灭。
depth = 3：按 $h$ 排序后先试染颜色 1，得到 **2/**2/221，此时 $h = 1$ ；再染 2、染 1 即完成，搜索在 3 步内命中。

可见估价函数把"先染 1"这种正确开局排到了最前，而 depth = 2 那一轮的失败又保证 3 就是最优解：既没有搜多余的最优深度以下的层，也没有在任何一层里漫无目的地枚举。