小明有一套玩具，一共包含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，否则按无效代码处理。 思路：扫描整个矩阵，对于每个矩形，我们可以从某个矩形的左上角向右扫描算出矩形的宽度，再从左上角向下扫描算出矩形的高度，然后用宽度乘以高度就能求出该矩形理论上应该有的部件数量，我们可以用一个数组存储每个矩形理论上的数量，再用一个数组标记该种类的矩形我们已经计算过它理论上部件的数量，下次我们不需要重新再计算，关于“矩形A中包含矩形B的部件，矩形B中包含矩形A同等数量部件"这个问题我们可以对矩形进行整体扫描，如果存在包含其它种类部件问题，直接“NO”。 扫描整个矩阵的同时我们可以顺便记录一下每个部件实际上在这个矩阵中个数，可以用数组进行存储。最后我们可以将每个矩形理论上的部件数量和实际上的部件数量进行核对，如何完全相同“YES”，否则"NO".
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static boolean []vis = new boolean[10]; public static void main(String[] args) { Scanner s = new Scanner(System.in); int t = s.nextInt(); ArrayList<String> list = new ArrayList<String>(); int n=0,m=0; char [][]map = null; for (int i = 0; i < t; i++) { n = s.nextInt(); m = s.nextInt(); map = new char[n][m]; for (int j = 0; j < n; j++) { map[j] = s.next().toCharArray(); } boolean result = check(map); list.add(result?"YES":"NO"); } for(String str: list) { System.out.println(str); } } private static boolean check(char[][] map) { int n = map.length,m = map[0].length; boolean vis[] = new boolean[10];//标记每种矩形是否计算过理论的部件数量 int M[] = new int[10];//用于记录每种矩形实际的部件数量 int count[] = new int[10];//用于记录每种矩形实际的部件数量 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int l = 0,r = 0,u = 0,d = 0; if(!vis[map[i][j]-'0']) { l = r = j; for (int x = j+1; x < m; x++) {//测量矩形宽度 if(x==m-1&&map[i][x]==map[i][j]) { r = x; break; }else if(map[i][x]!=map[i][j]) { r = x-1; break; } } u = d = i; for (int y = i+1; y < n; y++) {//测量矩形高度 if(y==n-1&&map[y][j]==map[i][j]) { d = y; break; }else if(map[i][j]!=map[y][j]) { d = y-1; break; } } if(!f(map,l,r,u,d)) return false; vis[map[i][j]-'0'] = true; M[map[i][j]-'0']=(r-l+1)*(d-u+1);//计算某个矩形的总的部件数量 } count[map[i][j]-'0']++; } } //将每个矩形理论上的部件数量和实际上的部件数量进行核对 for (int i = 0; i < M.length; i++) { if(M[i]!=count[i]) { return false; } } return true; } //用于判断某个矩形中是否包含了其它种类的部件 private static boolean f(char[][] map, int l, int r, int u, int d) { char s = map[u][l]; for (int i = u; i <=d; i++) { for (int j = l; j <=r; j++) { if(map[i][j]!=s)return false; } } return true; } }