網上搜了下棋盤覆蓋，結果看到了哈佛校訓。。。。
棋盤覆蓋是在一個2^k*2^k的棋盤中存在一個特殊格子，現要求用L型覆蓋整個棋盤（除特殊格子），問如何覆蓋這個棋盤？
在學校的時候，這題目是只看懂了解題思路，代碼沒仔細看過，現在在重新看的時候，感覺其實也不是那么難看懂！
先看解題思路截圖：
看到這個截圖你會有何感想呢？其實不就是個分治嘛！將一個2^k*2^k棋盤分割成4個2^(k-1)*2^(k-1),然后問題回到原點，在2^(k-1)*2^(k-1)棋盤中有一個特殊格子，求其用L型骨牌覆蓋方法！
代碼如下：
#include<stdio.h>
int Board[64][64];
int tile;
void ChessBoard(int tr,int tc,int dr,int dc,int size)//tr為棋盤左上角方格行號，tc為棋盤左上角列號，dr為特殊格行號，dc為特殊格列號，size=2^k，棋盤規格
{
if(size==1) //當分到只剩下一個格子的時候,該格就是本次遞歸特殊格
return ;
int t=++tile;
int 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,tc+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);
}
}
int main()
{
int i,j,k,l;
/**//*for(k=0;k<64;k++)
for(l=0;l<64;l++)
{ */
Board[2][1]=0;
tile=0;
ChessBoard(0,0,2,1,4);
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
printf("%d ",Board[i][j]);
}
printf("\n");
}
printf("\n");
// }
return 0;
}輸出結果：
哈佛校訓：
此刻打盹，你將做夢，此刻學習，你將圓夢！ 受教！！
posted on 2010-09-02 13:59
jince 閱讀(436)
評論(0) 編輯 收藏 引用 所屬分類:
算法設計與分析