蓝桥杯-java-b9-4-整理玩具

比眉伴天荒 2022-12-19 09:20 99阅读 0赞

package b9;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Scanner;
    
    /* * 小明有一套玩具，一共包含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 * */
    public class T4_整理玩具 { 
    
    	static boolean check(int[][] array,int i,int j) { 
    		int x0=j,y0=i;
    		// 找到x边界
    		for (int k = j; k <= array[i].length; k++) { 
    			if(k==array[i].length) { 
    				x0 = k-1;
    				break;
    			}
    			if(array[i][j]!=array[i][k]) { 
    				x0 = k-1;
    				break;
    			}
    		}
    		// 找到y边界
    		for (int k = i; k <= array.length; k++) { 
    			if(k==array.length) { 
    				y0 = k-1;
    				break;
    			}
    			if(array[i][j]!=array[k][j]) { 
    				y0 = k-1;
    				break;
    			}
    		}
    		// 判断其中是否有别的值
    		for (int k = i; k <= y0; k++) { 
    			for (int m = j; m <= x0; m++) { 
    				if(array[i][j]!=array[k][m]) { 
    					return false;
    				}
    			}
    		}
    		
    		// 将矩形赋值为 -1
    		for (int k = i; k <= y0; k++) { 
    			for (int m = j; m <= x0; m++) { 
    				array[k][m] = -1;
    			}
    		}
    		
    		return true;
    	}
    	
    	static boolean f(int[][] array) { 
    		
    		HashMap<Integer,Integer> map = new HashMap<>();
    		// n^2
    		for (int i = 0; i < array.length; i++) { 
    			for (int j = 0; j < array[0].length; j++) { 
    				int value = array[i][j];
    				if(map.get(value)!=null) { 
    					return false;
    				}
    				if(value==-1) { 
    					continue;
    				}
    				map.put(value, value);
    				
    				boolean b = check(array,i,j);
    				if(!b) { 
    					return false;
    				};
    			}
    		}
    		
    		return true;
    	}
    
    	public static void main(String[] args) { 
    		Scanner s = new Scanner(System.in);
    
    		int T = s.nextInt();
    		ArrayList<int[][]> list = new ArrayList<>();
    
    		for (int i = 0; i < T; i++) { 
    			int N = s.nextInt();
    			int M = s.nextInt();
    
    			int[][] array = new int[N][M];
    
    			s.nextLine();
    			
    			for (int j = 0; j < N; j++) { 
    				String str = s.nextLine();
    				String[] sArray = str.split("");
    				for (int k = 0; k < sArray.length; k++) { 
    					array[j][k] = Integer.valueOf(sArray[k]);
    				}
    			}
    			
    			list.add(array);
    		}
    		
    		for (int i = 0; i < list.size(); i++) { 
    			String result = f(list.get(i))?"YES":"NO";
    			System.out.println(result);
    		}
    	}
    }
    /* 1 2 3 4 int a1 = s.nextInt(); s.nextLine(); String s1 = s.nextLine(); int a2 = s.nextInt(); s.nextLine(); String s2 = s.nextLine(); System.out.println(a1); System.out.println(s1); System.out.println(a2); System.out.println(s2); 问题： 1. 读取整数之后读取行需要先读取一行 s.nextLine(),去掉换行 2. 边界问题一定要思考清楚 思路： 1. 遍历得到原始数据 2. 遍历原始数据的二维数组，得到不为 -1 的值必为顶点 3. 如果这个值之前出现过代表值重复，返回false 4. 如果没有出现过且不为 -1 检查该值所对应的边界，及边界内的矩形是否含有其他值 */