蓝桥杯2018年第九届真题-整理玩具-题解（Java代码）

解题思路:由题意可知 咱们需要把这个矩阵分为多个矩形来判断 判断的有一下几种

利用遍历的方式判断每一个元素 定义为判断元素

1. 在这个矩形(代码中 用长宽区域来表示)内部如果有跟这个判断元素不相等的 即为错

2. 如果上一个是正确的 那么如果在外面还有跟判断元素一样的 即为错

   
   

注意事项:

这里为了优化程序 把查找过的标记为-1 判断时直接跳过

参考代码:

package 整理玩具;

import java.util.Scanner;

public class Main {
 static int x;
 static int y;
 static int[][] a=new int[100][100];
public static void main(String[] args) {
 Scanner scanner=new Scanner(System.in);
 int N;
 int sum=0;
 int lenx=0,leny=0;
 N=scanner.nextInt();
 for(int i=0;i<N;i++){
  x=scanner.nextInt();
  y=scanner.nextInt();
  for(int ii=0;ii<x;ii++){
   char[] temp=scanner.next().toCharArray();
//   System.out.println(temp.length);
   for(int j=0;j<temp.length;j++){
    String l=String.valueOf(temp[j]);
    a[ii][j]=Integer.parseInt(l);
//    System.out.print(a[ii][j]);
   }
  }
  for(int ii=0;ii<x;ii++){
   for(int j=0;j<y;j++){
    if(a[ii][j]==-1){
    }else{
     int temp=bfs(ii,j);
     if(temp==1){
      sum++;
     }else{
      sum-=100;//-100 如果还觉着不放心可以放个-10000
     }
    }
   }
  }
  if(sum>0){
   System.out.println("YES");
   sum=0;//不会影响下一次判断
  }else{
   System.out.println("NO");
   sum=0;
  }
 }
}

private static int bfs(int lx, int ly) {
 // TODO Auto-generated method stub
 int tx=lx,ty=ly;
 for(int i=lx;i<x;i++){
  if(a[lx][ly]==a[tx][ly]){//判断往下是否有相等的
   tx++;//有的话就长度就加一
  }else{
   break;
  }
 }
 for(int i=ly;i<y;i++){
  if(a[lx][ly]==a[lx][ty]){//判断往右是否还有相等的
   ty++;//如果有宽度就加一
  }else{
   break;
  }
 }
 for(int i=0;i<x;i++){
  for(int j=0;j<y;j++){//遍历图中所有元素
   if(a[i][j]==-1){//如果这个数是-1 也就是之前判断过的 那就直接跳过
    
   }
   else if(i<tx&&j<ty&&i>lx&&a[lx][ly]==a[i][j]){
    a[i][j]=-1;//当在长度宽度范围内有相等的 就标记一下
   }else if(i<tx&&j<ty&&j>ly&&a[lx][ly]==a[i][j]){
    a[i][j]=-1;//当在长度宽度范围内有相等的 就标记一下
   }
   else if(i<tx&&j<ty&&i>lx&&j>ly&&a[lx][ly]!=a[i][j]){
    return -1;//如果在长度和宽度中又不相等的 直接推出去返回-1
   }
   //如果在长度和宽度范围外 还有相等 也是直接退出去
   else if(i>=tx&&a[lx][ly]==a[i][j]){//在长宽区域下边的
    return -1;
   }else if(j>=ty&&a[lx][ly]==a[i][j]){//在长宽区域右边的
    return -1;
   }else if(i<lx&&a[lx][ly]==a[i][j]){//在长宽区域上边的
    return -1;
   }else if(j<ly&&a[lx][ly]==a[i][j]){//在长宽区域左边的
    return -1;
   }
  }
 }
 return 1;//由上可知 只有在长宽里的元素都相等 而且外面没有长宽里的 元素时才会返回1
}
}