qipan.c

棋盘覆盖问题.用分治法设计L型组件填图问题的算法

#include"stdio.h"
#define maxsize 200
int c=1;
void play(int a[maxsize][maxsize],int x1,int y1,int x2,int y2,int s,int t)
{
	int n=x2-x1+1,k1,k2;

	if(n==2)
	{
		if(s==x1&&t==y1){a[x1][y2]=c;a[x2][y1]=c;a[x2][y2]=c;c++;}
		else if(s==x1&&t==y2){a[x1][y1]=c;a[x2][y1]=c;a[x2][y2]=c;c++;}
		else if(s==x2&&t==y1){a[x1][y1]=c;a[x1][y2]=c;a[x2][y2]=c;c++;}
		else {a[x1][y1]=c;a[x1][y2]=c;a[x2][y1]=c;c++;}
	}
	else 
	{
		k1=(x1+x2)/2;
		k2=(y1+y2)/2;

		if(s<=k1&&t<=k2)
		{a[k1][k2+1]=c;a[k1+1][k2]=c;a[k1+1][k2+1]=c;c++;
		 play(a,x1,y1,k1,k2,s,t);
		 play(a,x1,k2+1,k1,y2,k1,k2+1);
		 play(a,k1+1,y1,x2,k2,k1+1,k2);
		 play(a,k1+1,k2+1,x2,y2,k1+1,k2+1);
		}
		else if(s<=k1&&t>k2)
		{a[k1][k2]=c;a[k1+1][k2]=c;a[k1+1][k2+1]=c;c++;
		 play(a,x1,y1,k1,k2,k1,k2);
		 play(a,x1,k2+1,k1,y2,s,t);
		 play(a,k1+1,y1,x2,k2,k1+1,k2);
		 play(a,k1+1,k2+1,x2,y2,k1+1,k2+1);
		}
		else if(s>k1&&t<=k2)

		{a[k1][k2]=c;a[k1][k2+1]=c;a[k1+1][k2+1]=c;c++;
		 play(a,x1,y1,k1,k2,k1,k2);
		 play(a,x1,k2+1,k1,y2,k1,k2+1);
		 play(a,k1+1,y1,x2,k2,s,t);
		 play(a,k1+1,k2+1,x2,y2,k1+1,k2+1);
		}
		else 
		{a[k1][k2]=c;a[k1][k2+1]=c;a[k1+1][k2]=c;c++;
		 play(a,x1,y1,k1,k2,k1,k2);
		 play(a,x1,k2+1,k1,y2,k1,k2+1);
		 play(a,k1+1,y1,x2,k2,k1+1,k2);
		 play(a,k1+1,k2+1,x2,y2,s,t);
		}
	}

}




void main()
{
	int n,a[maxsize][maxsize],i,j;
    int s,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=-1;
	
	scanf("%d %d",&s,&t);
	a[s][t]=0;

     for(i=1;i<=n;i++)
	{for(j=1;j<=n;j++)
	 printf("%d     ",a[i][j]);
	 printf("\n");
	}

    play(a,1,1,n,n,s,t);
	for(i=1;i<=n;i++)
	{for(j=1;j<=n;j++)
	 printf("%3d",a[i][j]);
	  printf("\n");
	}
}