题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4787
把每个块共四个方向的都保存下来，然后 $n^2$ 判断就可以了。
网上没有题解，所以我来写一发。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include<bits/stdc++.h> #define maxn 120 #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ char ch[4][60][60]; }; int n,m,w,h; char c[maxn][maxn]; bool ban[5000]; vector<node>v; node tmp; inline bool bian_hang(int x){ for(int j=1; j<=m; j++)if(c[x][j]!='#')return false; return true; } inline bool bian_lie(int x){ for(int i=1; i<=n; i++)if(c[i][x]!='#')return false; return true; } inline void init(){ n=rd(),m=rd(); for(int i=1; i<=n; i++){ scanf("%s",c[i]+1); } for(int i=2; i<=n; i++){ if(bian_hang(i)){ h=i-2; break; } } for(int i=2; i<=m; i++){ if(bian_lie(i)){ w=i-2; break; } } } inline void make(int x,int y,int xx,int yy,int addx,int addy,int k){ if(k==0 || k==2){ for(int i=x,ii=1; i!=xx; i+=addx,ii++){ for(int j=y,jj=1; j!=yy; j+=addy,jj++){ tmp.ch[k][ii][jj]=c[i][j]; } } } else{ for(int j=y,ii=1; j!=yy; j+=addy,ii++){ for(int i=x,jj=1; i!=xx; i+=addx,jj++){ tmp.ch[k][ii][jj]=c[i][j]; } } } } inline bool check(int x,int y){ for(int kx=0; kx<4; kx++){ for(int ky=0; ky<4; ky++){ if(abs(kx-ky)!=0 && abs(kx-ky)!=2 && h!=w)continue; bool flag=true; int H,W; if(kx==0 || kx==2)H=h,W=w; else H=w,W=h; for(int i=1; i<=H; i++){ for(int j=1; j<=W; j++){ if(v[x].ch[kx][i][j]!=v[y].ch[ky][i][j]){ flag=false; break; } } if(!flag)break; } if(flag)return true; } } return false; } inline void work(){ for(int i=2; i<=n; i+=h+1){ for(int j=2; j<=m; j+=w+1){ make(i,j,i+h,j+w,1,1,0); make(i+h-1,j,i-1,j+w,-1,1,1); make(i+h-1,j+w-1,i-1,j-1,-1,-1,2); make(i,j+w-1,i+h,j-1,1,-1,3); v.pb(tmp); } } int ans=0; for(int i=0; i<v.size(); i++){ if(ban[i])continue; ans++; for(int j=i+1; j<v.size(); j++){ if(ban[j])continue; if(check(i,j))ban[j]=true; } } printf("%d\n",ans); } int main(){ init(); work(); return 0; } |
Orz