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. ^^