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 |
不容易啊~#include<iostream> using namespace std; int w, d, n, cnt; bool e[21][21][2];//1 right || 0 up bool v[21][21]; int x1, y1, x2, y2; int minx,maxx,miny,maxy; bool link(int i1, int j1, int i2, int j2) { if(i2==i1-1) return e[i2][j2][0]; if(j2==j1-1) return e[i2][j2][1]; if(i2==i1+1) return e[i1][j1][0]; if(j2==j1+1) return e[i1][j1][1]; } void DFS(int i, int j) { v[i][j]=1; if(i-1>=0 && v[i-1][j]==0 && !link(i,j,i-1,j)) //down DFS(i-1,j); if(j-1>=0 && v[i][j-1]==0 && !link(i,j,i,j-1)) //left DFS(i,j-1); if(i+1<w && v[i+1][j]==0 && !link(i,j,i+1,j)) //up DFS(i+1,j); if(j+1<d && v[i][j+1]==0 && !link(i,j,i,j+1)) //right DFS(i,j+1); } void draw() { int i; for(i=minx;i<maxx;i++) { if(miny>0) e[i][miny-1][1]=1; e[i][maxy-1][1]=1; } for(i=miny;i<maxy;i++) { if(minx>0) e[minx-1][i][0]=1; e[maxx-1][i][0]=1; } } int main() { while(scanf("%d%d",&w,&d)==2) { if(w==0 && d==0)break; cnt=0; scanf("%d",&n); memset(e,0,sizeof(e)); memset(v,0,sizeof(v)); int i, j; for(i=0;i<n;i++) { scanf("%d%d%d%d",&y1,&x1,&y2,&x2); maxx=(x1>=x2)?x1:x2; minx=(x1<=x2)?x1:x2; maxy=(y1>=y2)?y1:y2; miny=(y1<=y2)?y1:y2; draw(); } for(i=0;i<w;i++) for(j=0;j<d;j++) { if(!v[i][j]) { cnt++; DFS(i,j); } } printf("%d\n",cnt); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator