棋盘问题（未解决） 分治法.txt

ACM资料大集合

#include <stdio.h>
#include <cstdlib>


int board[8][8];
int t;//Ｌ牌号

void print()
{
	int size=8;
	int i,j;
	for(i=0;i<size;i++)
	{
		for(j=0;j<size;j++)
			printf("%2d",board[i][j]);
		printf("\n");
	}
	system("pause");
	printf("\n");
}

void check(int ti,int tj,int si,int sj,int size)
{
	//ti,tj表示棋盘左上角的坐标，si,sj表示特殊点的坐标,size表示棋盘大小
	int s;
	if(size==1) return;
	s=size/2;//划分棋盘
	t++;
	if(si<ti+s&&sj<tj+s)//左上角
		check(ti,tj,si,sj,s);
	else
	{
		board[ti+s-1][tj+s-1]=t;
		check(ti,tj,ti+s-1,tj+s-1,s);
		print();
	}
	if(si<ti+s&&sj>=tj+s)//右上角
		check(ti,tj+s,si,sj,s);
	else
	{
		board[ti+s-1][tj+s]=t;
		check(ti,tj+s,ti+s-1,tj+s,s);
		print();
	}
	if(si>=ti+s&&sj<tj+s)//左下角
		check(ti+s,tj,si,sj,s);
	else
	{
		board[ti+s][tj+s-1]=t;
		check(ti+s,tj,ti+s,tj+s-1,s);
		print();
	}
	if(si>=ti+s&&sj>=tj+s)//右下角
		check(ti+s,tj+s,si,sj,s);
	else
	{
		board[ti+s][tj+s]=t;
		check(ti+s,tj+s,ti+s,tj+s,s);
		print();
	}
}
int main()
{
	int size,ii,jj,i,j;
	scanf("%d %d %d",&size,&ii,&jj);
	t=0;
	check(0,0,ii,jj,size);
	for(i=0;i<size;i++)
	{
		for(j=0;j<size;j++)
			printf("%2d",board[i][j]);
		printf("\n");
	}
	return 0;
}