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);};
};
}