2383.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include"memory.h"
#include"stdio.h"

char map[1010][1010];
int next[1010][1010],X,Y,N;


struct point
{
	int x,y;
	int r,c;
}p[10100];

void init_next()
{
	int i,j;
	for(i=0;i<X;i++)
	for(j=0;j<Y;j++)
		next[i][j]=j+1;
};

void color(int x,int y,int r,int c)
{
	int st[1010],s;
	int i,j,up=x-r,down=x+r,left,right,t;
	if(up<0)up=0;
	if(down>=X)down=X-1;
	
	r*=r;
	for(i=up;i<=down;i++)
	{
		t=sqrt(r-(i-x)*(i-x));
		
		left=y-t,right=y+t;
		if(left<0)left=0;
		if(right>=Y)right=Y-1;

		s=0;
		for(j=left;j<=right;j=next[i][j])
		{
			if(map[i][j]==10)
				map[i][j]=c;
			st[s++]=j;
		}
		int k=j;
		while(k<Y&&map[i][k]!=10)
		{
			st[s++]=k;
			k=next[i][k];
		}
		while(s--)
			next[i][st[s]]=k;//next[i][right];
	}
}

void init()
{
	cin>>X>>Y>>N;
	for(int i=0;i<N;i++)
		cin>>p[i].x>>p[i].y>>p[i].r>>p[i].c;
	
	for(i=0;i<X;i++)
	for(int j=0;j<Y;j++)
		map[i][j]=10;
	
	init_next();
}
					
int main()
{
	init();
	for(int i=N-1;i>=0;i--)
		color(p[i].x,p[i].y,p[i].r,p[i].c);
	
	for(int j=0;j<Y;j++)
	{
		for(i=0;i<X;i++)
			printf("%c",map[i][j]%10+'0');
		printf("\n");
	}
	return 0;
}