chessboard.c

四个小算法。红黑树

#include "stdio.h"
#include "stdlib.h"
typedef struct CHE_RECT
{
	int tx;
	int ty;
	int bx;
	int by;
}CHE_RECT;

typedef struct FILL_POS
{
	int x;
	int y;
}FILL_POS;

int nFillColor;
CHE_RECT DivideFill(int nChessboard[16][16],CHE_RECT rect,FILL_POS pos);
int main()
{
	int nChessboard[16][16];
	int i,j;
	CHE_RECT rect;
	FILL_POS pos;
	for(i=0;i<16;++i)
	{
		for(j=0;j<16;++j)
			nChessboard[i][j]=0;
	}
	nFillColor=0;
	rect.tx=0;
	rect.ty=0;
	rect.bx=15;
	rect.by=15;
	pos.x=10;
	pos.y=3;
    DivideFill(nChessboard,rect,pos);
	for(i=0;i<16;++i)
	{
		for(j=0;j<16;++j)
			printf("%d ",nChessboard[i][j]);
		printf("\n");
	}
			
	return 1;
}

void FillCard(int nChessboard[16][16],int x,int y,int type,int color)
{
	int i,j;
	switch(type)
	{
	case 0:
		nChessboard[y][x]=color;
        nChessboard[y+1][x]=color;
		nChessboard[y+1][x+1]=color;
		break;
	case 1:
		nChessboard[y][x]=color;
        nChessboard[y][x+1]=color;
		nChessboard[y+1][x]=color;
		break;	
	case 2:
		nChessboard[y][x]=color;
        nChessboard[y][x+1]=color;
		nChessboard[y+1][x+1]=color;
		break;
	case 3:
		nChessboard[y][x+1]=color;
        nChessboard[y+1][x]=color;
		nChessboard[y+1][x+1]=color;
		break;
	}
	for(i=0;i<16;++i)
	{
		for(j=0;j<16;++j)
			printf("%d ",nChessboard[i][j]);
		printf("\n");
	}
	getchar();
}

CHE_RECT FillRect(int tx,int ty,int bx,int by)
{
	CHE_RECT tmprect;
    tmprect.tx=tx;
    tmprect.ty=ty;
    tmprect.bx=bx;
    tmprect.by=by;
	return tmprect;
}

CHE_RECT DivideFill(int nChessboard[16][16],CHE_RECT rect,FILL_POS pos)
{
	CHE_RECT tmprect;
	FILL_POS tmppos;
	int midx,midy;
	nFillColor++;
	nFillColor=nFillColor%9+1;

	if(rect.tx!=rect.bx && rect.ty!=rect.by)
	{
		midx=(rect.tx+rect.bx)/2;
        midy=(rect.ty+rect.by)/2;
		if(pos.x>midx && pos.y<=midy)
		{
			FillCard(nChessboard,midx,midy,0,nFillColor);
			tmprect=FillRect(rect.tx,rect.ty,midx,midy);
            tmppos.x=midx;
			tmppos.y=midy;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,rect.ty,rect.bx,midy);
            tmppos.x=pos.x;
			tmppos.y=pos.y;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,midy+1,rect.bx,rect.by);
            tmppos.x=midx+1;
			tmppos.y=midy+1;
            DivideFill(nChessboard,tmprect,tmppos);
            tmprect=FillRect(rect.tx,midy+1,midx,rect.by);
            tmppos.x=midx;
			tmppos.y=midy+1;
            DivideFill(nChessboard,tmprect,tmppos);
		}
		else if(pos.x<=midx && pos.y<=midy)
		{
			FillCard(nChessboard,midx,midy,3,nFillColor);
			tmprect=FillRect(rect.tx,rect.ty,midx,midy);
            tmppos.x=pos.x;
			tmppos.y=pos.y;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,rect.ty,rect.bx,midy);
            tmppos.x=midx+1;
			tmppos.y=midy;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,midy+1,rect.bx,rect.by);
            tmppos.x=midx+1;
			tmppos.y=midy+1;
            DivideFill(nChessboard,tmprect,tmppos);
            tmprect=FillRect(rect.tx,midy+1,midx,rect.by);
            tmppos.x=midx;
			tmppos.y=midy+1;
            DivideFill(nChessboard,tmprect,tmppos);
		}
		else if(pos.x<=midx && pos.y>midy)
		{
			FillCard(nChessboard,midx,midy,2,nFillColor);
			tmprect=FillRect(rect.tx,rect.ty,midx,midy);
            tmppos.x=midx;
			tmppos.y=midy;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,rect.ty,rect.bx,midy);
            tmppos.x=midx+1;
			tmppos.y=midy;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,midy+1,rect.bx,rect.by);
            tmppos.x=midx+1;
			tmppos.y=midy+1;
            DivideFill(nChessboard,tmprect,tmppos);
            tmprect=FillRect(rect.tx,midy+1,midx,rect.by);
			tmppos.y=pos.y;
            DivideFill(nChessboard,tmprect,tmppos);
		}
		else if(pos.x>midx && pos.y>midy)
		{
			FillCard(nChessboard,midx,midy,1,nFillColor);
			tmprect=FillRect(rect.tx,rect.ty,midx,midy);
            tmppos.x=midx;
			tmppos.y=midy;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,rect.ty,rect.bx,midy);
            tmppos.x=midx+1;
			tmppos.y=midy;
            DivideFill(nChessboard,tmprect,tmppos);
			tmprect=FillRect(midx+1,midy+1,rect.bx,rect.by);
            tmppos.x=pos.x;
			tmppos.y=pos.y;
            DivideFill(nChessboard,tmprect,tmppos);
            tmprect=FillRect(rect.tx,midy+1,midx,rect.by);
            tmppos.x=midx;
			tmppos.y=midy+1;
            DivideFill(nChessboard,tmprect,tmppos);
		}
	}

}