TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2440
  • 题目
  • P2440数字消除游戏
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 时限1000ms
    问题描述

        在一个n*n的方形棋盘上玩消除游戏,棋盘上布满了数字。
        每一步,玩家可以任选一个数字x,用它填充坐标为(1,1)格子所在连通区域,该区域的数字都会变成x。(如果两个数字相同且相邻,我们称这两个数字连通。相邻是上下左右四方向)。
        当整个棋盘的数字都相同时,就可以将整个棋盘上的数字消除掉,游戏结束。
        问,最少需要几次操作就能消除所有数字。
     

    输入格式

    有若干组测试数据(不超过20组),对于每组测试数据:
    第一行,一个整数n,表示棋盘的尺寸。
    接下来一个n*n的数字矩阵,表示游戏的初始局面。

    当输入的n==0时,输入结束。

    输出格式

    对于每组测试数据,输出一行,一个整数,表示最少需要的操作数。

    样例输入

    2
    1 3 
    3 3
    4
    5 5 2 0
    5 5 2 0
    2 2 2 0
    0 0 0 2
    0

    样例输出

    1
    3

    提示

    样例说明,对于第二组数据:
    第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种不同的数字