text.txt

设B是一个n×n棋盘

L型组件填图问题
1.问题描述
设B是一个n×n棋盘，n=2k,(k=1,2,3,…)。用分治法设计一个算法，使得：用若干个L型条块可以覆盖住B的除一个特殊方格外的所有方格。其中，一个L型条块可以覆盖3个方格。且任意两个L型条块不能重叠覆盖棋盘。
    例如：如果n=2，则存在4个方格，其中，除一个方格外，其余3个方格可被一L型条块覆盖；当n=4时，则存在16个方格，其中，除一个方格外，其余15个方格被5个L型条块覆盖。
#include<stdio.h>
//i,j为表示棋盘的数组A[0...n-1][0...n-1]中值为1的元素下标，其余元素为0
//初始化：b=3;Lmap(A,0,n-1,0,n-1, i,j,&b,n);
void Lmap(int A[],int t,int u,int r,int s,int i,int j,int *b,int n)
{int a,k,h,mid1=(u+t)/2,mid2=(r+s)/2;
if(mid1+1<=i&&i<=u&&mid2+1<=j&&j<=s)a=1;
if(t<=i&&i<=mid1&&mid2+1<=j&&j<=s)a=2;
if(mid1+1<=i&&i<=u&&r<=j&&j<=mid2)a=3;
if(t<=i&&i<=mid1&&r<=j&&j<=mid2)a=4;
if(u-t==1&&s-r==1)
{for(k=0;k<2;k++)for(h=r;h<r+2;h++)if(!A[(t+k)*n+h])A[(t+k)*n+h]=*b;(*b)++;}
else
{
if(a==1)
{A[mid1*n+mid2]= A[mid1*n+mid2+1]= A[(mid1+1)*n+mid2]=2;
Lmap(A,t,mid1,r,mid2,mid1,mid2,b,n);
Lmap(A,mid1+1,u,r,mid2,mid1+1,mid2,b,n);
Lmap(A,t,mid1,mid2+1,s,mid1,mid2+1,b,n);
Lmap(A,mid1+1,u,mid2+1,s,i,j,b,n);};
if(a==2)
{A[mid1*n+mid2]= A[(mid1+1)*n+mid2+1]= A[(mid1+1)*n+mid2]=2;
Lmap(A,t,mid1,r,mid2,mid1,mid2,b,n);
Lmap(A,mid1+1,u,r,mid2,mid1+1,mid2,b,n);
Lmap(A,t,mid1,mid2+1,s,i,j,b,n);
Lmap(A,mid1+1,u,mid2+1,s,mid1+1,mid2+1,b,n);};
if(a==3)
{A[mid1*n+mid2]= A[mid1*n+mid2+1]= A[(mid1+1)*n+mid2+1]=2;
Lmap(A,t,mid1,r,mid2,mid1,mid2,b,n);
Lmap(A,mid1+1,u,r,mid2,i,j,b,n);
Lmap(A,t,mid1,mid2+1,s,mid1,mid2+1,b,n);
Lmap(A,mid1+1,u,mid2+1,s,mid1+1,mid2+1,b,n);};
if(a==4)
{A[mid1*n+mid2+1]= A[(mid1+1)*n+mid2+1]= A[(mid1+1)*n+mid2]=2;
Lmap(A,t,mid1,r,mid2,i,j,b,n);
Lmap(A,mid1+1,u,r,mid2,mid1+1,mid2,b,n);
Lmap(A,t,mid1,mid2+1,s,mid1,mid2+1,b,n);
Lmap(A,mid1+1,u,mid2+1,s,mid1+1,mid2+1,b,n);};
};
}