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种不同的数字