ZOJ 2975 思维-白红宇

ZOJ 2975 思维

阅读量：6909 次

发布时间：2019-06-27

本文共 972 字，大约阅读时间需要 3 分钟。

题意给出一个矩形问在其中存在多少子矩形其四个角上的字母是一样的

一开始暴力写了一发先枚举行数再枚举两个列数再向下枚举行数判断能否没有意外的超时了

后来想了想当我们已经确定两个列数的时候向下寻找的时候如果找到了tot条边与第一条边同字母这些边可以组成（tot-1）*tot个矩形使满足题意

为了避免重复寻找需要一个map来记录由于矩形的边最长100 我们存已经检索的字母*1000*1000+左列数*1000+右列数

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;int n,m;char a[300][300];int main(){ int t; scanf("%d",&t); while(t--) { map
           
            q; q.clear(); int sum=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n-1;i++) { for(int k=1;k<=m-1;k++) { for(int j=k+1;j<=m;j++) { if(a[i][k]!=a[i][j]) continue; int x=a[i][k]-'A'; if(q[x*1000000+k*1000+j]!=0) continue; int tot=1; for(int l=i+1;l<=n;l++) { if(a[l][j]==a[l][k]&&a[l][j]==a[i][j]) { tot++; q[x*1000000+k*1000+j]=1; } } sum+=(tot-1)*tot/2; } } } printf("%d\n",sum); }}