6971: BZOJ2971：魔法森林

       你一定听说过魔法森林吧。难道没有吗？至少从精灵的传说里听说过它吧？虽然没有人知道它到底在那里，但许许多多的传说证明了它的存在。比如有人说，没有人进了魔法森林，还能找到回来的路。无论如何，人们知道魔法森林是一个矩形，如果我们把它分成单位正方形，在每个正方形里正好有一棵树。如果你有时间去听村里最年长的老者讲故事，他们甚至会告诉你关于魔法森林的更奇异的事情。        这个魔法森林是怎样来的呢？魔法森林最初只是普通的森林，在它周围很远的地方都没有其他森林。但是有一天……这是春天里的一个阳光灿烂的日子，森林里的所有居民都很高兴。但突然一声熊猫的吼叫宣告了伟大的森林议会就要开始了。所有动物放下它们的工作，立即赶往议会。其中刺猬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。

提示

没有写明提示

题目来源

没有写明来源