# The ninth final of the blue bridge cup-D_ Finishing toys:

# Title:

Xiao Ming has a set of toys, including NxM parts in total. These parts are placed in a toy box containing NxM small squares, and exactly one part is placed in each small lattice. Each part is marked with an integer from 0 to 9, and multiple parts may be marked with the same integer. Xiao Ming has special requirements for the placement of toys: parts marked with the same integer must be placed together to form a rectangular shape. If the following placement meets the requirements:00022

00033

44444

12244

12244

12233

01234

56789

The following placement does not meet the requirements:

11122

11122

33311

111111

122221

122221

111111

11122

11113

33333

Please judge whether it meets Xiaoming's requirements.

input

The input contains multiple sets of data.

The first row contains an integer t representing the number of data groups. (1 <= T <= 10)

The following contains group T data.

The first row of each set of data contains two integers n and m. (1 <= N, M <= 10)

The following matrix contains N rows and M columns, representing the placement mode.

output

For each group of data, the output of YES or NO represents whether it meets Xiaoming's requirements.

[sample input]

3

3 5

00022

00033

44444

3 5

11122

11122

33311

2 5

01234

56789

[sample output]

YES

NO

YES

Resource agreement:

Peak memory consumption (including virtual machine) < 256M

CPU consumption < 1000ms

# Problem solving ideas:

## 1 - variable creation:

(1). The integer variable x used to control several sets of data.

(2). The shaping variable m used to control the number of data rows in each group and the shaping variable n used to control the number of columns.

(3). The string array variable s used to receive M and N (the reason is explained in detail below)

(4). The string array variable str used to receive each row in each group of data

(5). The Boolean array variable result used to store the result

Obtain the corresponding data through the console, then judge each group of data, store it in the result variable, and finally output the corresponding YES or NO according to the result variable

## 2 - problem solving difficulties:

Highlight: the inspection part is used to check whether this group of data meets the placement standards

First of all, we need to find a way to judge whether it is rectangular. In fact, it is very easy to understand that if toys of each category need to be stored together, there should be no other types of toys in the rectangular box formed from the first data to the last data, such as:

00111

00011

00111

In this placement method, we check whether it is qualified according to the above ideas. Since the position of the first "0" is (0,0) and the position of the last "0" is (2,1), there are NO other game types in the rectangular box of (0,0) - (2,1), At this time, the placement result of this group of data is still YES (don't mistakenly think we have made an error). Continue. The position of the first "1" is (0,2) and the position of the last "1" is (2,4). In the rectangular box of (0,2) - (2,4), it is obvious that there is a toy "0", which is unqualified. Once an unqualified toy appears, Then this set of data is NO

Of course, if there is only one type of each toy, it is also true, for example:

01234

56789

For "0", there is no other toy type between (0,0) - (0,0)

Through these two examples, we can also find that we need to find the initial point (where it appears for the first time) and the end point (where it appears for the last time) of each toy type. There is no need to repeat the search of these two points.

Therefore, we use the method of box selection rectangle to judge whether a group of data meets the conditions we need

Fine node: console acquisition part

If we write as follows

package Blue Bridge Cup training set; import java.util.Scanner; public class Console acquisition { public static void main(String[] args) { @SuppressWarnings("resource") Scanner in = new Scanner(System.in); int x = in.nextInt(); for(int i=0;i<x;i++) { System.out.println("row"+i); String str = in.nextLine(); } } } Get instance from console: 4 row0 row1 123 row2 456 row3 789

There is no doubt that we will always input one less line. I don't know the specific reason. I understand that this may be because x doesn't encounter carriage return when obtaining the integer value. When we hit carriage return, it runs directly into for, so we can get the value directly from line 1 instead of line 0

Solution: we directly let the process of obtaining the value of x also be obtained through one line. Because shaping cannot obtain one line of data, we added string variables. The specific implementation is as follows (this is also the detailed explanation of the third point of creating variables):

package Blue Bridge Cup training set; import java.util.Scanner; public class Console acquisition { public static void main(String[] args) { @SuppressWarnings("resource") Scanner in = new Scanner(System.in); String s1 = in.nextLine(); int x = Integer.valueOf(s1); for(int i=0;i<x;i++) { System.out.println("row"+i); String str = in.nextLine(); } } } Get instance from console: 4 row0 This is zero row1 This is one row2 This is two row3 This is three

After solving the above two problems, this problem can run according to our ideas

# Code implementation:

public class d_Tidy toys { static int startx; static int starty;//Coordinates of the starting point of the toy static int endx; static int endy;//Coordinates of the end point of the toy static int flage =0;//It is used to judge whether a group of data conforms to the rules static int m; static int n;//Well known m and n, rows and columns public static void main(String[] args) { @SuppressWarnings("resource") Scanner in = new Scanner(System.in);//instantiation String s1 = in.nextLine();//The part of the above solution obtained by the console is explained in detail String[] s; //An array of characters holding m and n int x = Integer.valueOf(s1); boolean[] result = new boolean[x];//Create a result variable based on the amount of data for(int i=0;i<x;i++){//The next step is to get the console s = in.nextLine().split(" "); m=Integer.valueOf(s[0]); n=Integer.valueOf(s[1]); String[] str = new String[m]; for(int j=0;j<m;j++){ str[j] = in.nextLine(); } int[][] map = new int [m][n];//Create shaping variables to store data for(int k=0;k<m;k++){//Fill variable for(int l=0;l<str[k].length();l++){ map[k][l]=Integer.valueOf(str[k].charAt(l)-48);//Because the difference between characters and numbers is 48 So cut it off } } if(checkzong(map)){//inspect result[i]=true; }else { result[i]=false; } } for(boolean f:result){//Enhanced for traversal and output results if(f){ System.out.println("YES"); }else { System.out.println("NO"); } } } public static void checkstart(int x,int[][] map){//Used to find the initial point for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(map[i][j]==x){ startx = i; starty = j; return ; } } } } public static void checkend(int x,int[][] map){//Used to find the end point for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(map[i][j]==x){ endx = i; endy = j; } } } } public static boolean checktrue(int x,int startx,int starty,int endx,int endy,int[][] map)//It is used to judge whether this group of data is qualified, and only judge whether x meets the rules { for(int i=startx;i<=endx;i++){ for(int j=starty;j<endy;j++){ if(map[i][j]!=x){ return false; } } } return true; } public static boolean checkzong(int[][] map) {//Used to judge all toy types from 0 to 9 flage =0; for(int i=0;i<=9;i++){ startx=0; starty=0; endx=0; endy=0; checkstart(i,map); checkend(i,map); if(!checktrue(i,startx,starty,endx,endy,map)){ flage =1; break; } } if(flage==1){ return false; }else { return true; } } }

The code may be a little cumbersome. If you have a better understanding, please give me some advice. ^^