Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
200 行C++,极不清晰,仅供参考#include <iostream> #include <vector> #include <memory> using namespace std; const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; typedef bool arr[105][105]; struct Tcon { int h,w; bool map[105][105]; }; Tcon t1,t2,t3,t4; bool m[105][105],vis[105][105],vis2[105][105],used[12000]; int t,w,h,n,x,y,tot,MAXx,MAXy,MINx,MINy; vector<Tcon> map1; Tcon temp; bool ok (Tcon A,Tcon B) { if ((A.h!=B.h)||(A.w!=B.w)) return false; for (int iii=1;iii<=A.w;iii++) for (int jjj=1;jjj<=A.h;jjj++) if (A.map[iii][jjj]!=B.map[iii][jjj]) return false; return true; } void fan1() { memset(t4.map,false,sizeof(t4.map)); for (int ii=1;ii<=t3.w;ii++) for (int jj=1;jj<=t3.h;jj++) t4.map[ii][jj]=t3.map[t3.w-ii+1][jj]; memset(t3.map,false,sizeof(t3.map)); for (int ii=1;ii<=t3.w;ii++) for (int jj=1;jj<=t3.h;jj++) t3.map[ii][jj]=t4.map[ii][jj]; } void fan2() { memset(t4.map,false,sizeof(t4.map)); for (int ii=1;ii<=t3.w;ii++) for (int jj=1;jj<=t3.h;jj++) t4.map[ii][jj]=t3.map[ii][t3.h-jj+1]; memset(t3.map,false,sizeof(t3.map)); for (int ii=1;ii<=t3.w;ii++) for (int jj=1;jj<=t3.h;jj++) t3.map[ii][jj]=t4.map[ii][jj]; } void zhuan() { memset(t4.map,false,sizeof(t4.map)); for (int ii=1;ii<=t3.h;ii++) for (int jj=1;jj<=t3.w;jj++) t4.map[ii][jj]=t3.map[jj][t3.h+1-ii]; swap(t3.h,t3.w); memset(t3.map,false,sizeof(t3.map)); for (int ii=1;ii<=t3.w;ii++) for (int jj=1;jj<=t3.h;jj++) t3.map[ii][jj]=t4.map[ii][jj]; } bool equal() { if (!(((t1.h==t2.h) && (t1.w==t2.w))||((t1.h==t2.w) && (t1.w==t2.h)))) return false; if (ok(t1,t2)) return true; t3=t1; fan1(); if (ok(t2,t3)) return true; fan2(); if (ok(t2,t3)) return true; fan1(); if (ok(t2,t3)) return true; t3=t1; for (int REP=1;REP<=3;REP++) { zhuan(); if (ok(t2,t3)) return true; fan1(); if (ok(t2,t3)) return true; fan2(); if (ok(t2,t3)) return true; fan1(); if (ok(t2,t3)) return true; fan2(); } return false; } bool find(Tcon t) { for (int ii=0;ii<tot;ii++) { if (!used[ii]) { t1=t; t2=map1[ii]; if (equal()) { used[ii]=true; return true; } } } return false; } void calc(int x,int y) { vis2[x][y]=true; MAXx=max(MAXx,x); MAXy=max(MAXy,y); MINx=min(MINx,x); MINy=min(MINy,y); for (int ii=0;ii<=3;ii++) { if ((!vis2[x+dir[ii][0]][y+dir[ii][1]]) && (m[x+dir[ii][0]][y+dir[ii][1]])) calc(x+dir[ii][0],y+dir[ii][1]); } } void ff(int x,int y) { vis[x][y]=true; temp.map[x-MINx+1][y-MINy+1]=true; for (int ii=0;ii<=3;ii++) { if ((!vis[x+dir[ii][0]][y+dir[ii][1]]) && (m[x+dir[ii][0]][y+dir[ii][1]])) ff(x+dir[ii][0],y+dir[ii][1]); } } int main() { cin>>t; for (int tt=1;tt<=t;tt++) { map1.clear(); memset(m,false,sizeof(m)); memset(vis,false,sizeof(vis)); cin>>w>>h>>n; for (int j=1;j<=n;j++) { cin>>x>>y; m[x+1][y+1]=true; } tot=0; memset(vis2,false,sizeof(vis2)); for (int i=1;i<=w;i++) for (int j=1;j<=h;j++) { if ((!vis[i][j]) && m[i][j]) { MAXx=0,MAXy=0; MINx=200000000,MINy=20000000; tot++; memset(temp.map,false,sizeof(temp.map)); calc(i,j); temp.h=MAXy-MINy+1; temp.w=MAXx-MINx+1; ff(i,j); map1.push_back(temp); } } memset(m,false,sizeof(m)); memset(vis,false,sizeof(vis)); memset(vis2,false,sizeof(vis2)); memset(used,false,sizeof(used)); for (int j=1;j<=n;j++) { cin>>x>>y; m[x+1][y+1]=true; } bool ans=true; for (int i=1;i<=w;i++) { for (int j=1;j<=h;j++) { if ((!vis[i][j]) && m[i][j]) { MAXx=0,MAXy=0; MINx=200000000,MINy=20000000; memset(temp.map,false,sizeof(temp.map)); calc(i,j); temp.h=MAXy-MINy+1; temp.w=MAXx-MINx+1; ff(i,j); if (!find(temp)) { ans=false; break; } } } if (!ans) break; } if (ans) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator