three.c

四个小算法。红黑树

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
//#define MAX 1024
static int count=1;
int m;

void Dispatch_Fill(int y,int x,int start_y,int end_y,int start_x,int end_x,int *p)
{
	int sx1,sx2,sx3,sx4,sy1,sy2,sy3,sy4;

	if(start_x==end_x || start_y==end_y)//in fact,judge start_y==end_y is just for beautiful
		return;

	sx1=start_x;
	sx2=(end_x-start_x+1)/2+start_x-1;
	sx3=sx2+1;
	sx4=end_x;

	sy1=start_y;
	sy2=(end_y-start_y+1)/2+start_y-1;
	sy3=sy2+1;
	sy4=end_y;
//	printf("%d	%d	%d	%d\n",sx1,sx2,sx3,sx4);
	
	if(sx1<=x && x<=sx2 && sy1<=y && y<=sy2){
		*(p+sx2*(int)pow(2,m)+sy3)=count;
		*(p+sx3*(int)pow(2,m)+sy3)=count;
		*(p+sx3*(int)pow(2,m)+sy2)=count++;
		Dispatch_Fill(y,x,sy1,sy2,sx1,sx2,p);
        	Dispatch_Fill(sy3,sx2,sy3,sy4,sx1,sx2,p);
        	Dispatch_Fill(sy3,sx3,sy3,sy4,sx3,sx4,p);
        	Dispatch_Fill(sy2,sx3,sy1,sy2,sx3,sx4,p);
	}
	else if(sx1<=x && x<=sx2 && sy2<y && y<=sy4){
		*(p+sx2*(int)pow(2,m)+sy2)=count;
		*(p+sx3*(int)pow(2,m)+sy3)=count;
		*(p+sx3*(int)pow(2,m)+sy2)=count++;
		Dispatch_Fill(sy2,sx2,sy1,sy2,sx1,sx2,p);
        	Dispatch_Fill(y,x,sy3,sy4,sx1,sx2,p);
        	Dispatch_Fill(sy3,sx3,sy3,sy4,sx3,sx4,p);
        	Dispatch_Fill(sy2,sx3,sy1,sy2,sx3,sx4,p);
	}
	else if(sx2<x && x<=sx4 && sy2<y && y<=sy4){
		*(p+sx2*(int)pow(2,m)+sy2)=count;
		*(p+sx2*(int)pow(2,m)+sy3)=count;
		*(p+sx3*(int)pow(2,m)+sy2)=count++;
		Dispatch_Fill(sy2,sx2,sy1,sy2,sx1,sx2,p);
        	Dispatch_Fill(sy3,sx2,sy3,sy4,sx1,sx2,p);
        	Dispatch_Fill(y,x,sy3,sy4,sx3,sx4,p);
        	Dispatch_Fill(sy2,sx3,sy1,sy2,sx3,sx4,p);
	}
	else if(sx2<x && x<=sx4 && sy1<=y && y<=sy2){
		*(p+sx2*(int)pow(2,m)+sy2)=count;
		*(p+sx2*(int)pow(2,m)+sy3)=count;
		*(p+sx3*(int)pow(2,m)+sy3)=count++;
	        Dispatch_Fill(sy2,sx2,sy1,sy2,sx1,sx2,p);
        	Dispatch_Fill(sy3,sx2,sy3,sy4,sx1,sx2,p);
        	Dispatch_Fill(sy3,sx3,sy3,sy4,sx3,sx4,p);
        	Dispatch_Fill(y,x,sy1,sy2,sx3,sx4,p);
	}
	return;
}

int main(int argc,char **argv)
{
	int i,j,x,y,*p;
	
	printf("please input the Index you want to input:	");
	scanf("%d",&m);
	printf("please input the x coordinate about the specified:	");
	scanf("%d",&x);
	printf("please input the y coordinate about the specified:	");
	scanf("%d",&y);
	
	p=(int *)malloc(sizeof(int)*(pow(2,m)+1)*(pow(2,m)+1));
	for(i=1;i<=pow(2,m);i++)
		for(j=1;j<=pow(2,m);j++)
			*(p+i*(int)pow(2,m)+j)=-1;
	*(p+x*(int)(pow(2,m))+y)=0;
	Dispatch_Fill(y,x,1,pow(2,m),1,pow(2,m),p);	//(y,x),(1,pow(2,m)),(1,pow(2,m)),p
	for(i=1;i<=pow(2,m);i++)
	{
		for(j=1;j<=pow(2,m);j++)
		{
			if(*(p+i*(int)pow(2,m)+j)<0)
			{
				printf("%d  ",*(p+i*(int)pow(2,m)+j));
			}
			else if(*(p+i*(int)pow(2,m)+j)<10)
			{
				printf("%d   ",*(p+i*(int)pow(2,m)+j));
			}
			else if(*(p+i*(int)pow(2,m)+j)<100)
			{
				printf("%d  ",*(p+i*(int)pow(2,m)+j));
			}
			else 
			{
				printf("%d ",*(p+i*(int)pow(2,m)+j));
			}
		}
		printf("\n");
	}
	free(p);
	return 0;
}