思路简单的暴力解法

解题思路:

    对于每一个数字，判断是否组成矩形的思路是：找到该数字能形成的最大的面积与该数字的数量是否相等，若相等，则是矩阵

    下图表示什么是能形成的最大矩阵：得到最大矩阵的思路就是再遍历该数字时动态的更新该矩阵的左上角坐标和右下角坐标

    注意事项:

参考代码:

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader = new Scanner(System.in);
		int t = reader.nextInt();
		int[] result = new int[t];//保存输出的结果
		for(int i=0;i<t;i++) {
			int n = reader.nextInt();
			int m = reader.nextInt();
			int[][] mat = new int[n][m];
			Set<Integer> set = new HashSet<>();// 计算一下这组数据中有几个数
			for(int j=0;j<n;j++) {
				String b = reader.next();
				for(int k=0;k<m;k++) {
					mat[j][k] = b.charAt(k) - 48;
					set.add(mat[j][k]);
				}
			}
			// 对每个矩阵进行分析，保存结果
			if(show(mat,set)) {
				result[i] = 1;
			}
			set.clear();
		}
		// 输出结果
		for(int i=0;i<t;i++) {
			if(result[i]==1)
				System.out.println("YES");
			else {
				System.out.println("NO");
			}
		}
	}
	// 思路： 遍历矩阵中的每个数，保存每个数所组成矩阵的左上角和右下角坐标依次来计算面积
	// 若所得矩阵面积与该数的个数相同，则是矩阵，反之则不是	
	private static boolean show(int[][] a,Set<Integer> set) {
		boolean flag = true;
		// 遍历每个数
		for(int e : set) {
			// 初始化左上角与右下角坐标
			int[] start = {Integer.MAX_VALUE,Integer.MAX_VALUE};
			int[] end = {Integer.MIN_VALUE,Integer.MIN_VALUE};
			int count = 0; // 记录数量
			for(int i=0;i<a.length;i++) {
				for(int j=0;j<a[0].length;j++) {
					if(a[i][j] == e) {
						// 当前点坐标小于或等于左下角，进行替换
						if(i<=start[0]&&j<=start[1]) {
							start[0] = i;
							start[1] = j;
						}
						// 当前点坐标大于或等于右上角，进行替换
						if(i>=end[0]&&j>=end[1]) {
							end[0] = i;
							end[1] = j;
						}
						count ++;	
					}
				}
			}
			// 计算矩阵面积跟数量是否相等
			int x = end[0] - start[0] +1;
			int y = end[1] - start[1] +1;
			// 若不等，则返回false
			if(x*y!=count) {
				flag = false;
				break;
			}	
		}
		
		return flag;
	}

}