Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不容易啊~

Posted by qq312873977 at 2009-05-16 12:14:17 on Problem 3338
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator