http://acm.pku.edu.cn/JudgeOnline/problem?id=1021
Код:
#include<iostream> #include<vector> using namespace std; vector< vector<int> > s1,s2; void print(int a[100][100]); void find(int a[100][100],int num); void gene(int a[100][100]); vector<int> sortt(vector<int> s); vector< vector<int> > get(int a[100][100]); int t,w,h,n,x,y,countt; int main() { cin>>t; for(int i=0;i<t;i++) { int a[100][100]={0}; int b[100][100]={0}; cin>>w>>h>>n; for(int j=0;j<n;j++){cin>>x>>y;a[y][x]=1;} for(int j=0;j<n;j++){cin>>x>>y;b[y][x]=1;} gene(a); vector< vector<int> > ss1=get(a); gene(b); vector< vector<int> > ss2=get(b); for(int j=0;j<ss1.size();j++)ss1[j]=sortt(ss1[j]); for(int j=0;j<ss2.size();j++)ss2[j]=sortt(ss2[j]); if(ss1.size()==ss2.size()) { vector<int> flag(ss1.size(),0); for(int j=0;j<ss1.size();j++) { for(int k=0;k<ss2.size();k++) { if(flag[k]!=1&&ss1[j].size()==ss2[k].size()) { int l; for(l=0;l<ss1[j].size();l++) { if(ss1[j][l]!=ss2[k][l])break; } if(l==ss1[j].size()) { flag[k]=1; } } } } int m; for(m=0;m<flag.size();m++) { if(flag[m]!=1)break; } if(m!=flag.size()) { cout<<"NO"<<endl; } else { cout<<"YES"<<endl; } } else { cout<<"NO"<<endl; } } return 0; } vector< vector<int> > get(int a[100][100]) { vector<int> temp; vector< vector<int> > ss(countt-1,temp); for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { if(a[i][j]!=0) { int noof=0; int xs[8]={i-1,i-1,i-1,i,i,i+1,i+1,i+1}; int ys[8]={j-1,j,j+1,j-1,j+1,j-1,j,j+1}; for(int k=0;k<8;k++) { if(xs[k]>-1&&xs[k]<h&&ys[k]>-1&&ys[k]<w) { if(a[xs[k]][ys[k]]==a[i][j]) { noof++; } } } ss[a[i][j]-2].push_back(noof); } } } return ss; } void gene(int a[100][100]) { find(a,1); countt=1; while(x!=-1&&y!=-1) { vector<int> xx(1,x),yy(1,y); a[x][y]=countt+1; while(xx.size()!=0) { vector<int> tmpx,tmpy; for(int i=0;i<xx.size();i++) { int xs[4]={xx[i]-1,xx[i],xx[i],xx[i]+1}; int ys[4]={yy[i],yy[i]-1,yy[i]+1,yy[i]}; for(int k=0;k<4;k++) { if(xs[k]>-1&&xs[k]<h&&ys[k]>-1&&ys[k]<w) { if(a[xs[k]][ys[k]]==1) { a[xs[k]][ys[k]]=countt+1; tmpx.push_back(xs[k]); tmpy.push_back(ys[k]); } } } } xx=tmpx; yy=tmpy; } countt++; find(a,1); } } vector<int> sortt(vector<int> s) { for(int i=0;i<s.size()-1;i++) { for(int j=0;j<s.size()-1;j++) { if(s[j]>s[j+1]) { s[j]=s[j]+s[j+1]; s[j+1]=s[j]-s[j+1]; s[j]=s[j]-s[j+1]; } } } return s; } void find(int a[100][100],int num) { x=-1;y=-1; for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { if(a[i][j]==num) { x=i; y=j; return; } } } } void print(int a[100][100]) { cout<<endl; for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { cout<<a[i][j]; }cout<<endl; }cout<<endl; }