WebService之CXF注解之三（Service接口实现类）

标签：style   blog   class   code   ext   color   

Leo has a grid with N rows and M columns. All cells are painted with either black or white initially.

Two cells A and B are called connected if they share an edge and they are in the same color, or there exists a cell C connected to both A and B.

Leo wants to paint the grid with the same color. He can make it done in multiple steps. At each step Leo can choose a cell and flip the color (from black to white or from white to black) of all cells connected to it. Leo wants to know the minimum number of steps he needs to make all cells in the same color.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N and M (1 N, M N lines follow. Each line contains a string with N characters. Each character is either ‘X‘ (black) or ‘O‘ (white) indicates the initial color of the cells.

Output

For each test case, output the minimum steps needed to make all cells in the same color.

Sample Input

2
2 2
OX
OX
3 3
XOX
OXO
XOX

Sample Output

1
2

Hint

For the second sample, one optimal solution is:

Step 1. flip (2, 2)

XOX
OOO
XOX

Step 2. flip (1, 2)

XXX
XXX
XXX

题意：

给你一个染色的 N×M 的格子，你每次可以选择一个连通块，将其颜色取反。问最后将整个格子变为同色的最小步数。

思路：

其实就是一个最短路，将连通块缩点然后不同种的连通块之间连边，那么将整个格子变为同色的最小步数就等于一个点到地图上最远点的距离了。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include