Flood-it 游戏

题目描述

Flood-it 是谷歌+平台上的非常好玩的一款游戏。

在游戏开始时，系统将随机生成 $N \times N$ 的方形区域，并且区域内的每个网格都被涂成了六种颜色中的一种（颜色编号为 0 到 5）。

游戏规则

1. 起始位置：玩家从**左上角(1,1)**开始游戏。
2. 操作步骤：在每个步骤中，玩家选择一种颜色并将与左上角连通的所有格子（包括左上角）都变成该种颜色。
3. 连通定义：两个格子有公共边，并且颜色相同。
4. 游戏目标：通过这种方式，玩家从左上角开始将所有格子都变为同一种颜色，求最少步数。

输入格式

输入包含不超过 20 个测试用例。

每个测试用例：

• 第一行包含一个整数 $N$，表示方形区域大小
• 接下来 $N$ 行，每行包含 $N$ 个整数（0-5），第 $i$ 行第 $j$ 个整数表示第 $i$ 行第 $j$ 列的格子的颜色
• 当输入样例 $N=0$ 时，表示输入终止，该用例无需处理

输出格式

每个测试用例输出一个占据一行的整数，表示所需最少步数。

数据范围

$2 \leq N \leq 8$

输入样例

2
0 0 
0 0
3
0 1 2
1 1 2
2 2 1
0

输出样例

0
3

样例解释

第一个测试用例：$N=2$

初始网格：
0 0
0 0

左上角已经是颜色0，并且所有格子都是颜色0。
所有格子已经是同一种颜色，不需要任何操作。
输出：0

第二个测试用例：$N=3$

初始网格：
0 1 2
1 1 2
2 2 1

步骤分析（一种可能的解法）：
初始状态：左上角区域包含(1,1)，颜色为0
步骤1：选择颜色1，左上角区域变为颜色1，连通区域扩大
        网格变为：
        1 1 2
        1 1 2
        2 2 1
步骤2：选择颜色2，左上角区域变为颜色2，连通区域扩大
        网格变为：
        2 2 2
        2 2 2
        2 2 1
步骤3：选择颜色1，左上角区域变为颜色1，所有格子颜色相同
        网格变为：
        1 1 1
        1 1 1
        1 1 1

共需要3步，输出：3

游戏过程可视化

题目中的图示显示了 $4 \times 4$ 游戏的最早步骤：

初始网格：

0 0 0 0
0 1 1 1
0 1 2 2
0 1 2 3

步骤：

1. 初始：左上角为颜色0
2. 选择颜色1：将左上角连通区域变为颜色1
3. 选择颜色2：将左上角连通区域变为颜色2
4. 选择颜色3：将左上角连通区域变为颜色3
5. ...直到所有格子颜色相同

注意事项

1. 连通区域：每次操作影响的是与左上角连通的所有同色格子，不仅仅是直接相邻的格子。
2. 颜色选择：每次可以选择六种颜色（0-5）中的任意一种，不一定是当前连通区域的颜色。
3. 最少步数：目标是找到将所有格子变为同一种颜色的最小操作次数。
4. 网格大小：$N$ 最大为8，相对较小，可以使用搜索算法。

时空限制

• 时间限制：1秒
• 空间限制：64MB