#105. 涂满它!

涂满它!

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Flood-it是谷歌 +平台上的非常好玩的一款游戏,游戏界面如下所示:

img

在游戏开始时,系统将随机生成N×N\red{N \times N}的方形区域,并且区域内的每个网格都被涂成了六种颜色中的一种。

玩家从左上角开始游戏。

在每个步骤中,玩家选择一种颜色并将与左上角连通的所有格子(包括左上角)都变成该种颜色。

这里连通定义为:两个格子有公共边,并且颜色相同。

通过这种方式,玩家可以从左上角开始将所有格子都变为同一种颜色。

下图显示了4×4\red{4 \times 4}游戏的最早步骤(颜色标记为 0\red 05\red 5):

img

请你求出,给定最初区域以后,最少要多少步才能把所有格子的颜色变成一样的。

输入格式

输入包含不超过20\red{20}个测试用例。 每个测试用例,第一行包含一个整数N\red N,表示方形区域大小。 接下里 N\red N 行,每行包含N\red N个整数05\red{(0-5)},第 i\red i 行第 j\red j 个整数表示第 i\red i 行第 j\red j 列的格子的颜色。 当输入样例 N=0\red{N=0} 时,表示输入终止,该用例无需处理。

输出格式

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

样例

输入样例

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

输出样例

0
3

提示

2N8\red{2≤N≤8}

搜索强化

未参加
状态
已结束
规则
IOI
题目
13
开始于
2022-7-25 9:00
结束于
2022-7-26 9:00
持续时间
24 小时
主持人
参赛人数
30