魔法森林

时间限制:10s      空间限制:128MB

题目描述

       你一定听说过魔法森林吧。难道没有吗?至少从精灵的传说里听说过它吧?虽然没有人知道它到底在那里,但许许多多的传说证明了它的存在。比如有人说,没有人进了魔法森林,还能找到回来的路。无论如何,人们知道魔法森林是一个矩形,如果我们把它分成单位正方形,在每个正方形里正好有一棵树。如果你有时间去听村里最年长的老者讲故事,他们甚至会告诉你关于魔法森林的更奇异的事情。
       这个魔法森林是怎样来的呢?魔法森林最初只是普通的森林,在它周围很远的地方都没有其他森林。但是有一天……这是春天里的一个阳光灿烂的日子,森林里的所有居民都很高兴。但突然一声熊猫的吼叫宣告了伟大的森林议会就要开始了。所有动物放下它们的工作,立即赶往议会。其中刺猬Harry来得最慢,于是鸟们开始没有耐性地唱歌,苍蝇们开始飞来飞去(不断地),野鹿开始发出一些奇怪地声音,老狐狸正在狡猾地观察着她身边的所有东西,而那只大黑熊又开始感到饥饿了,于是它开始用草莓充饥。没有人知道将会发生什么,没有人——除了Olivia——一只聪明的猫头鹰。
 
—我亲爱的朋友们,我相信每个人都同意这点——我们的森林不能让一个游客的眼睛感到非常愉快。森林里有太多种树了。更确切地说,有两种——松树和柏树。我们应该把其中一种树全部消灭掉。你们建议消灭哪种呢?
-“谁在乎呢……”大黑熊喃喃自语地说道,然后它又一口把另一个草莓吃了下去。大多数其他的动物都感到非常困惑,它们都没有听明白。
-好了,接下来我要问第二个问题了:我们应该怎样干掉那些树呢?Olivia说道。
 
       就在这个时候,一个巫师在一束亮光之下出现了。(在这之前他一直藏在一棵树后面。)他的名字是Genzibabel。事实上,这些消灭树的计划都是他的主意——他想练习一下他刚学会的魔法。于是他开始对动物们说:
 
-我可以把你们的森林里的树全部变成其中一种。我可以施展一种叫做Floodfill-Altertree的魔法。我需要做的只是选定其中一棵树,然后我会施展魔法。在魔法放出的一瞬间,我选中树所在的一片和它相同种类的树都会变成另外一种树(也就是说,松树变成柏树,柏树变成松树)。用这个方法,我可以用一次魔法就把一整片相同树的连接区域变成另外一种。但是施展这个魔法是非常辛苦的(要耗费MP啊!),所以我想尽可能少地使用这个魔法。
 
要记住,我们可以把森林想象成由树组成的矩形。两棵树相邻当且仅当他们所在的单位正方形有公共边。你要解决的问题正和这个巫师还有这些动物们一样。你要求出最少要施展多少次魔法才可以把所有的树只变成一种。


输入格式

输入文件的第一行有一个数B,表示下面有B组数据。每组数据第一行有两个整数R,C(1<=R,C<=150),表示森林的行数和列数。再下面是一个R行C列的01矩阵,表示森林。1表示松树,0表示柏树。矩阵的任何位置没有空格。


输出格式

     每组数据输出一行,每行一个整数:最少施展魔法的次数。


样例输入

2
1 10
1011001101
9 9
001111100
010000010
100101001
100101001
100000001
101000101
100111001
010000010
001111100

样例输出

3
2
【样例解释】
第一组数据依次在(1,2),(1,9),(1,5)施法,第二组依次在(2,3),(3,1)施法。
【数据约定】
1≤R,C≤150。
对于40%的数据有R*C≤35*35。

提示

没有写明提示


题目来源

没有写明来源