蓝桥杯2018年第九届真题-整理玩具(思路简单)

解题思路:
注意到n，m，t较小,考虑暴力解法。

相等的数字在一起并且是矩形要求:1.每一行相等的数字是连续段，2.对于任意一个数字，它在每一行连续段的出现起点与出现终点一致。

利用数组minn[i][j]记录数字j在第i行的起始位置，mxxx[i][j]记录数字j在第i行的终点位置，sum[i][j]记录数字j在第i行的出现次数。

对于条件1，要求mxxx[i][j]-minn[i][j]+1==sum[i][j],因为对于一行，所有可能的数字j的位置均在minn[i][j]与mxxx[i][j]间，等式左边计算的是这包括起点终点的长度，只有长度就是数字出现次数时，才能这段长度里全是这个数字，即数字连续。

对于条件2，在条件1的基础上要求mxxx[i][j]==mxxx[x][j](mxxx[x][j]!=0) 和minn[i][j]==minn[x][j](mxxx[x][j]!=INF) 

复杂度O(T*m*n)
注意事项:
注意细节，数组初始化等。
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define maxx 13
int v,e,k,a,b,n,m,t,x,y,l,r,neww,neww2,w,ans=0,q,noww,ans1,ans2;
int sum[maxx][maxx];
int minn[maxx][maxx];
int mxxx[maxx][maxx];
int smax[maxx];
int smin[maxx];
int all[maxx][maxx];
string s;


int main()
{
  cin>>t;
  for(int i=1;i<=t;++i)
 {cin>>n>>m;
 for(int i=1;i<=n;++i)
    {cin>>s;
    for(int j=1;j<=m;++j)
    all[i][j]=s[j-1]-'0';
    }
    ans=0;
   for(int i=1;i<=n;++i)
    for(int j=0;j<=9;++j)
     {sum[i][j]=0;
     minn[i][j]=INF;
     mxxx[i][j]=0;
     }
 for(int j=0;j<=9;++j)
  {smax[j]=0;
  smin[j]=INF;}

  for(int i=1;i<=n;++i)
     for(int j=1;j<=m;++j)
      {++sum[i][all[i][j]];
      minn[i][all[i][j]]=min(minn[i][all[i][j]],j);
      mxxx[i][all[i][j]]=max(mxxx[i][all[i][j]],j);
      }
 
    for(int i=1;i<=n;++i)
    for(int j=0;j<=9;++j)
     {if(minn[i][j]==INF&&mxxx[i][j]==0) continue;
      if(mxxx[i][j]-minn[i][j]+1!=sum[i][j]) ans=1;
      if(smax[j]==0) smax[j]=mxxx[i][j];
      if(smin[j]==INF) smin[j]=minn[i][j];
     }

      for(int i=1;i<=n;++i)
    for(int j=0;j<=9;++j)
     {if(minn[i][j]==INF&&mxxx[i][j]==0) continue;
      if(smax[j]!=mxxx[i][j]) ans=1;
      if(smin[j]!=minn[i][j]) ans=1;
     }
       
     
   
  if(ans==0) cout<<"YES\n";
  else cout<<"NO\n";
 }
}