棋盘覆盖算法(分治算法)

就说在一个2的K次方乘以2的K次方的棋盘里,又一个特殊的方格,那么这个就叫做特殊棋盘,比方说又一个4行4列的棋盘,第2行2列与其他方格不同(其他方格是空白,它是阴影),那么这个就叫做特殊棋盘了,好,要实现的是用一个L形状的骨牌来覆盖除特殊方格以外的其他方格,要求任何2个L骨牌不得重复,算法如下:(请大家讨论哦)听取各位大侠的意见:

C++算法的:

#include "iostream.h"
#include "iomanip.h"
#define N 8
class qipan
{
public:
void chessBoard(int tr,int tc,int dr,int dc,int size)
{

   if(size==1)return;
 
   int t=tile++,s=size/2;
   if(dr<tr+s&&dc<tc+s)
    chessBoard(tr,tc,dr,dc,s);
    else
   {
    board[tr+s-1][tc+s-1]=t;
    chessBoard(tr,tc,tr+s-1,tc+s-1,s);
   }
 
   if(dr<tr+s&&dc>=tc+s)
    chessBoard(tr,tc+s,dr,dc,s);
   else
   {
 
    board[tr+s-1][tc+s]=t;
    chessBoard(tr,tc+s,tr+s-1,tc+s,s);
   }

   if(dr>=tr+s&&dc<tc+s)
    chessBoard(tr+s,tc,dr,dc,s);
   else
   {
 
    board[tr+s][tc+s-1]=t;
    chessBoard(tr+s,tc,tr+s,tc+s-1,s);
   }

   if(dr>=tr+s&&dc>=tc+s)
    chessBoard(tr+s,tc+s,dr,dc,s);
   else
   {
 
    board[tr+s][tc+s]=t;
    chessBoard(tr+s,tc+s,tr+s,tc+s,s);
   }
 
  
}

public:
int tile,tr,tc,dr,dc,size;
int board[N][N];



};


void main()
{
qipan q;
q.tile=0;


for(int i1=1;i1<=N;i1++)
{
for(int j1=1;j1<=N;j1++)
   q.board[i1][j1]=0;
}
   q.board[2][2]=-1;
q.chessBoard(1,1,2,2,N);

for(int i=1;i<=N;i++)
{
   for(int j=1;j<=N;j++){
    cout<<setw(4)<<q.board[j];}
   cout<<endl;
}


}