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