小明有一套玩具，一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中，每个小格子中恰好摆放一个部件。
每一个部件上标记有一个0~9的整数，有可能有多个部件标记相同的整数。
小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。
如以下摆放是满足要求的：
00022
00033
44444
12244
12244
12233
01234
56789
以下摆放不满足要求：
11122
11122
33311
111111
122221
122221
111111
11122
11113
33333
给出一种摆放方式，请你判断是否符合小明的要求。
输入
输入包含多组数据。
第一行包含一个整数T，代表数据组数。 (1 <= T <= 10)
以下包含T组数据。
每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10)
以下包含N行M列的矩阵，代表摆放方式。
输出
对于每组数据，输出YES或者NO代表是否符合小明的要求。
【样例输入】
3
3 5
00022
00033
44444
3 5
11122
11122
33311
2 5
01234
56789
【样例输出】
YES
NO
YES
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
PS：
分析
一开始想着用连通性做，发现挺麻烦的，后来主要思考矩形这个条件限制，想到了一个非常巧妙的做法。
既然是矩形，那就必然有固定的长和宽，那么我们为每一种玩具设置矩形的边界值，用maxX、maxY、minX、minY来确定矩形的范围。先假设所有的玩具都是符合在一个矩形中这个条件。读取数据不断更新更新矩形的边界，最后比较每种矩形是否有重叠的部分，如果有，说明存在不在一个矩形内的玩具，则是NO。
注：矩形重叠的充分必要条件是：横轴上矩形A的右边界值大于等于矩形B的左边界值且矩形A的左边界值小于等于矩形B的右边界值，同时竖轴上矩形A的上边界值大于等于矩形B的下边界值且矩形A的下边界值小于等于矩形B的上边界值。
import java.util.Scanner;;
class Fanwei {
int minX;
int maxX;
int minY;
int maxY;
Fanwei() {
minX = minY = maxX = maxY = -10;
}
}
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; i++)
{
boolean res = true;
Fanwei[] fanwei = new Fanwei[10];
for (int j = 0; j < 10; j++)
fanwei[j] = new Fanwei();
int N = in.nextInt();
int M = in.nextInt();
in.nextLine();
int[][] gezi = new int[N][M];
for (int j = 0; j < N; j++)
{
char[] str = in.nextLine().toCharArray();
for (int k = 0; k < M; k++)
{
gezi[j][k] = str[k]-48;
}
}
for (int j = 0; j < N; j++)
{
for (int k = 0; k < M; k++)
{
int tmp = gezi[j][k];
if (fanwei[tmp].minX == -10 || fanwei[tmp].minX > j)
fanwei[tmp].minX = j;
if (fanwei[tmp].maxX == -10 || fanwei[tmp].maxX < j)
fanwei[tmp].maxX = j;
if (fanwei[tmp].minY == -10 || fanwei[tmp].minY > k)
fanwei[tmp].minY = k;
if (fanwei[tmp].maxY == -10 || fanwei[tmp].maxY < k)
fanwei[tmp].maxY = k;
}
}
OUT:
for (int j = 0; j < 9; j++)
{
if (fanwei[j].minX == -10)
continue;
for (int k = j+1; k < 10; k++)
{
if (fanwei[k].minX == -10)
continue;
if (fanwei[j].maxX >= fanwei[k].minX && fanwei[j].minX <= fanwei[k].maxX)
{
if (fanwei[j].maxY >= fanwei[k].minY && fanwei[j].minY <= fanwei[k].maxY)
{
res = false;
break OUT;
}
}
}
}
if (res)
System.out.println("YES");
else
System.out.println("NO");
}
}
}