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

增加水题的ac人数。。

Posted by zsgkfeng at 2009-06-11 14:04:54 on Problem 3338
#include<iostream>
#include<cstdio>
#include<algorithm>
#define fo(i,u,d) for(int i=u;i<=d;i++)
using namespace std;
const int d[5][3]={{0,0,0},{0,-1,0},{0,0,1},{0,1,0},{0,0,-1}};
int re,n,m,ans,x1,y1,x2,y2;
bool a[50][50][5],u[50][50];
void swap(int& x,int&y){
	int z=x;
	x=y;
	y=z;
}
void init(){
	cin>>re;
	memset(a,0,sizeof(a));
	fo(i,1,re){
		cin>>x1>>y1>>x2>>y2;
		x1++;y1++;x2++;y2++;
		if (x1>x2)swap(x1,x2);
		if (y1>y2)swap(y1,y2);
		fo(y,y1,y2-1){
			a[x1][y][1]=true;
			a[x1-1][y][3]=true;
			a[x2-1][y][3]=true;
			a[x2][y][1]=true;
		}
		fo(x,x1,x2-1){
			a[x][y1][4]=true;
			a[x][y1-1][2]=true;
			a[x][y2-1][2]=true;
			a[x][y2][4]=true;
		}
	}
}
void dfs(int x,int y){
	u[x][y]=true;
	fo(i,1,4){
		int nx=x+d[i][1];
		int ny=y+d[i][2];
		if ((!u[nx][ny])&&(nx>0)&&(ny>0)&&(nx<n)&&(ny<m)&&(!a[x][y][i]))
			dfs(nx,ny);
	}
}
void work(){
	memset(u,0,sizeof(u));
	ans=0;
	fo(i,1,n-1)
		fo(j,1,m-1)
			if (!u[i][j]){
				ans++;
				dfs(i,j);
			}
	cout<<ans<<endl;
}
int main(){

	for(cin>>n>>m;n+m;cin>>n>>m){
		n++;m++;
		swap(n,m);
		init();
		work();
	}
	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