| ||||||||||
| 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 | |||||||||
呵呵,此题数据太弱。你的蒙分算法如下吧~In Reply To:惊讶:蒙分算法0ms过! Posted by:AllwaysDead at 2008-09-29 17:30:46 #include <cstdio>
#include <string.h>
using namespace std;
int father[10000];
int findfather(int a){return father[a]==-1?a:father[a]=findfather(father[a]);}
void together(int a,int b){if (findfather(a)!=findfather(b))father[findfather(a)]=findfather(b);}
int map1[100][100],map2[100][100],map3[100][100],W,H,colors1[10000][6],colors2[10000][6];
int T2(int a){return a*a;}
int Minn(int a,int b){if (a<b)return T2(b);return T2(a);}
int main(){
int N,s,i,x,y,j;
scanf("%d",&N);
while (N--){
memset(map1,0,sizeof(map1));memset(map2,0,sizeof(map2));
scanf("%d %d %d",&W,&H,&s);
for (i=0;i<s;i++){scanf("%d %d",&x,&y);map1[y][x]=-1;}
for (i=0;i<s;i++){scanf("%d %d",&x,&y);map2[y][x]=-1;}
memset(father,0xff,sizeof(father));
for (x=0;x<H;x++)for (y=0;y<W;y++)if (map1[x][y]){
if (x>0 && map1[x-1][y])together(x*100+y,(x-1)*100+(y));
if (y>0 && map1[x][y-1])together(x*100+y,(x)*100+(y-1));
if (x+1<H && map1[x+1][y])together(x*100+y,(x+1)*100+(y));
if (y+1<W && map1[x][y+1])together(x*100+y,(x)*100+(y+1));
}
memset(colors1,0xff,sizeof(colors1));
for (x=0;x<H;x++)for (y=0;y<W;y++)if (map1[x][y]){i=map1[x][y]=findfather(x*100+y)+1;i--;
colors1[i][0]++;
if (colors1[i][1]==-1 || colors1[i][1]>x)colors1[i][1]=x;
if (colors1[i][2]==-1 || colors1[i][2]<x)colors1[i][2]=x;
if (colors1[i][3]==-1 || colors1[i][3]>y)colors1[i][3]=y;
if (colors1[i][4]==-1 || colors1[i][4]<y)colors1[i][4]=y;
}
for (x=0;x<H;x++)for (y=0;y<W;y++)if ((i=map1[x][y]-1)>=0)
colors1[i][5]+=Minn(x-colors1[i][1],colors1[i][2]-x)+Minn(y-colors1[i][3],colors1[i][4]-y);
memset(father,0xff,sizeof(father));
for (x=0;x<H;x++)for (y=0;y<W;y++)if (map2[x][y]){
if (x>0 && map2[x-1][y])together(x*100+y,(x-1)*100+(y));
if (y>0 && map2[x][y-1])together(x*100+y,(x)*100+(y-1));
if (x+1<H && map2[x+1][y])together(x*100+y,(x+1)*100+(y));
if (y+1<W && map2[x][y+1])together(x*100+y,(x)*100+(y+1));
}
memset(colors2,0xff,sizeof(colors2));
for (x=0;x<H;x++)for (y=0;y<W;y++)if (map2[x][y]){i=map2[x][y]=findfather(x*100+y)+1;i--;
colors2[i][0]++;
if (colors2[i][1]==-1 || colors2[i][1]>x)colors2[i][1]=x;
if (colors2[i][2]==-1 || colors2[i][2]<x)colors2[i][2]=x;
if (colors2[i][3]==-1 || colors2[i][3]>y)colors2[i][3]=y;
if (colors2[i][4]==-1 || colors2[i][4]<y)colors2[i][4]=y;
}
for (x=0;x<H;x++)for (y=0;y<W;y++)if ((i=map2[x][y]-1)>=0)
colors2[i][5]+=Minn(x-colors2[i][1],colors2[i][2]-x)+Minn(y-colors2[i][3],colors2[i][4]-y);
for (x=0;x<10000;x++)if (colors1[x][0]!=-1){
colors1[x][2]-=colors1[x][1];
colors1[x][4]-=colors1[x][3];
if (colors1[x][4]<colors1[x][2]){y=colors1[x][4];colors1[x][4]=colors1[x][2];colors1[x][2]=y;}
}
for (x=0;x<10000;x++)if (colors2[x][0]!=-1){
colors2[x][2]-=colors2[x][1];
colors2[x][4]-=colors2[x][3];
if (colors2[x][4]<colors2[x][2]){y=colors2[x][4];colors2[x][4]=colors2[x][2];colors2[x][2]=y;}
}
for (j=0;j<10000;j++)if (colors1[j][0]!=-1){
for (i=0;i<10000 && (!(colors1[j][0]==colors2[i][0] && colors1[j][2]==colors2[i][2] &&
colors1[j][4]==colors2[i][4] && colors1[j][5]==colors2[i][5]));i++);
if (i==10000){puts("NO");break;}
colors2[i][0]=-1;
}
if (j==10000)puts("YES");
}
getchar();getchar();getchar();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator