第28題
（棋盤覆蓋問題）在一個 k k 2 × 2 個方格組成的棋盤中恰有一個方格與其他方格不同（圖中標(biāo)記為
-1 的方格），稱之為特殊方格?，F(xiàn)用 L 型（占 3 個小格）紙片覆蓋棋盤上除特殊方格的所有部分，各紙
片不得重疊，于是，用到的紙片數(shù)恰好是(4 ?1)/ 3 k 。在下表給出的一個覆蓋方案中，k=2，相同的 3
個數(shù)字構(gòu)成一個紙片。
下面給出的程序是用分治法設(shè)計的，將棋盤一分為四，依次處理左上角、右上角、左下角、右下角，
遞歸進(jìn)行。請將程序補(bǔ)充完整。
#include <iostream.h>
#include <iomanip.h>
int board[65][65],tile; // tile 為紙片編號
void chessboard(int tr,int tc,int dr,int dc,int size)
// dr,dc 依次為特殊方格的行、列號
{
int t,s;
if (size==1)
⑤ ;
t=tile++;
s=size/2;
if( ⑥ )
chessboard(tr,tc,dr,dc,s);
else
{
board[tr+s-1][tc+s-1]=t;
⑦ ;
}
if(dr<tr+s && dc>=tc+s)
chessboard(tr,tc+s,dr,dc,s);
else
{
board[tr+s-1][tc+s]=t;
⑧ ;
}
if(dr>=tr+s && dc<tc+s)
chessboard(tr+s,tc,dr,dc,s);
else
{
board[tr+s][tc+s-1]=t;
⑨ ;
}
if(dr>=tr+s && dc>=tc+s)
chessboard(tr+s,tc+s,dr,dc,s);
else
{
board[tr+s][tc+s]=t;
⑩ ;
}
}
void prt1(int b[][65],int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<setw(3)<<b[i][j];
cout<<endl;;
}
}
void main()
{
int size,dr,dc;
cout<<"input size(4/8/16/64):"<<endl;
cin>>size;
cout<<"input the position of special block(x,y):"<<endl;
cin>>dr>>dc;
board[dr][dc]=-1;
tile++;
chessboard(1,1,dr,dc,size);
prt1(board,size);
}