2597. [POJ 4007] 涂满它！

【题目描述】

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

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

玩家从左上角开始游戏。

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

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

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

下图显示了 4×4 游戏的最早步骤（颜色标记为 0 到 5）：

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

【输入格式】

每个测试点包含多组数据。

每组数据的第一行是一个整数N，表示地摊上的格子有N行N列。

接下来一个N*N的矩阵，矩阵中的每个数都在0~5之间，描述了每个格子的颜色。

N=0代表输入的结束。

【输出格式】

对于每组数据，输出一个整数，表示最少步数。

【样例输入】

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

【样例输出】

0
3

【数据规模与约定】

对于30%的数据，N<=5

对于50%的数据，N<=6

对于70%的数据，N<=7

对于100%的数据，N<=8，每个测试点不多于20组数据。