| ||||||||||
| 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