中文
日本語
English
| P2440数字消除游戏 | ||
|
Description
在一个n*n的方形棋盘上玩消除游戏，棋盘上布满了数字。
每一步，玩家可以任选一个数字x，用它填充坐标为(1,1)格子所在连通区域，该区域的数字都会变成x。（如果两个数字相同且相邻，我们称这两个数字连通。相邻是上下左右四方向）。
当整个棋盘的数字都相同时，就可以将整个棋盘上的数字消除掉，游戏结束。
问，最少需要几次操作就能消除所有数字。
Input Format
有若干组测试数据(不超过20组)，对于每组测试数据：
第一行，一个整数n，表示棋盘的尺寸。
接下来一个n*n的数字矩阵，表示游戏的初始局面。
当输入的n==0时，输入结束。
Output Format
对于每组测试数据，输出一行，一个整数，表示最少需要的操作数。
Sample Input 1
2
1 3
3 3
4
5 5 2 0
5 5 2 0
2 2 2 0
0 0 0 2
0
Sample Output 1
1
3
Sample Input 2
1
2
2
1 1
0 0
3
5 5 4
4 5 4
0 0 4
3
2 5 5
1 3 1
5 1 2
3
3 0 3
0 2 3
4 4 3
3
2 2 5
5 0 5
0 3 4
3
5 1 1
0 5 3
2 3 3
0
Sample Output 2
0
1
2
5
4
4
5
Hint
样例说明，对于第二组数据：
第1步 选数字2去填充，得到：
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 2
第2步 选数字0去填充，得到：
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
第3步 选数字2去填充，得到：
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
对于100%的数据，n<=8,
初始棋盘中最多有6种不同的数字