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 |
看,我的70l,就是速度有点慢In Reply To:居然一次AC,分享下代码,仅供参考,140行C++,0ms Posted by:sbtdkj1017 at 2010-09-13 23:35:05 #include<iostream> #include<stdio.h> #include<map> #define MAXN 110 #define MAXM 300010 #define MO 19931219 #define FOR(i,l,r) for (i=l;i<=r;i++) #define COR(i,r,l) for (i=r;i>=l;i--) #define M(a) memset(a,0,sizeof(a)) using namespace std; map <unsigned int,int> Map; int i,j,k,l,m,n,ca,tim,bet; static int a[2][MAXN][MAXN],q[MAXN][MAXN],cx[MAXM],cy[MAXM]; const int wy[4]={0,-1,0,1},wx[4]={1,0,-1,0}; bool check(int x,int y) { return (x && x<=n && y && y<=m);} unsigned int ram(int fri) { return bet=(bet*fri+234645)%MO;} void flood(int x,int y,int g,int dx,int dy,int co) { int l1=0,l2=1,fin,nx,ny,i,j,k; cx[1]=x;cy[1]=y;q[x][y]=1; unsigned int hash=19931219;bet=hash; while (l1<l2) for (x=cx[++l1],y=cy[l1],k=0;k<=3;k++) { nx=x+wx[(k+g)%4]*dx;ny=y+wy[(k+g)%4]*dy; if (check(nx,ny) && a[co][nx][ny] && !q[nx][ny]) { q[nx][ny]=1;cx[++l2]=nx;cy[l2]=ny; hash=((hash+ram(l1))*k+ram(l2)*(k*k+12))*(k+hash+2345); } } if (co) Map[hash]++; else if (Map[hash]) { Map[hash]--; FOR(i,1,l2) a[0][cx[i]][cy[i]]=0; } } int main() { for (scanf("%d",&ca);ca;ca--,M(a)) { scanf("%d%d%d",&n,&m,&tim); FOR(i,1,tim) { scanf("%d%d",&j,&k);j++;k++; a[0][j][k]=1;} FOR(i,1,tim) { scanf("%d%d",&j,&k);j++;k++; a[1][j][k]=1;} M(q);FOR(i,1,n) FOR(j,1,m) if (a[1][i][j] && !q[i][j]) flood(i,j,0,1,1,1); M(q);FOR(i,1,n) FOR(j,1,m) if (a[0][i][j] && !q[i][j]) flood(i,j,0,1,1,0); M(q);COR(i,n,1) FOR(j,1,m) if (a[0][i][j] && !q[i][j]) flood(i,j,0,-1,1,0); M(q);FOR(j,1,m) COR(i,n,1) if (a[0][i][j] && !q[i][j]) flood(i,j,3,1,1,0); M(q);COR(j,m,1) COR(i,n,1) if (a[0][i][j] && !q[i][j]) flood(i,j,3,1,-1,0); M(q);COR(i,n,1) COR(j,m,1) if (a[0][i][j] && !q[i][j]) flood(i,j,2,1,1,0); M(q);FOR(i,1,n) COR(j,m,1) if (a[0][i][j] && !q[i][j]) flood(i,j,2,-1,1,0); M(q);COR(j,m,1) FOR(i,1,n) if (a[0][i][j] && !q[i][j]) flood(i,j,1,1,1,0); M(q);FOR(j,1,m) FOR(i,1,n) if (a[0][i][j] && !q[i][j]) flood(i,j,1,1,-1,0); FOR(i,1,n) { FOR(j,1,m) if (a[0][i][j]) break; if (j<=m) break; } if (i>n && j>m) printf("YES\n"); else printf("NO\n"); Map.clear(); } return 1; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator