jake1036

My Links

Blog Stats

Posts - 101
Stories - 0
Comments - 23
Trackbacks - 0

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

分治法之棋盤分割問題

/*

該算法適宜使用分治法解決

(1) 含有4的k次方個方格的棋盤。

(2) 在其中的一個方格中有一個特殊的棋子，現在打算將L型的骨牌覆蓋到棋盤中。

(3) 要求除了那一個特殊的棋子之外，其余的格子均可以由L型骨牌覆蓋。

解決方法:

(1) 將整個棋盤等分成4塊，每塊2的(k-1)次方個棋格。

(2) 判斷每一個小的棋盤，若特殊棋子在這個小棋盤中，則按相同的方法遞歸處理這個小棋盤。

(3) 若這個小棋盤中不存在特殊棋子，則就根據該棋盤的位置，來分別進行處理。

(4) 若該棋盤在原來棋盤的左上，則在小棋盤的右下方設置一個特殊字符。

(5) 若該棋盤在原來棋盤的右上，則在小棋盤的左下方設置一個特殊字符。

(6) 若該棋盤在原來棋盤的左下，則在小棋盤的右上方設置一個特殊字符。

(7) 若該棋盤在原來棋盤的右下，則在小棋盤的左上方設置一個特殊字符。

經過4 , 5 , 6 ,7各個步驟，則各個子問題轉換為與原問題相同的問題。

*/

#include <stdio.h>

#define M 8

int tile = 1 ; //表示當前的紙牌編號

int board [M][M] ;

/*

tr 棋盤左上角的行坐標

tc 棋盤左上角的列坐標

dr 特殊棋子的行坐標

dc 特殊棋子的列坐標

*/

void chessBoard(int tr , int tc , int dr , int dc , int size)

{

if(size == 1) //遞歸結束條件

return ;

int t = tile++ , s = size / 2; //t表示當前的紙牌號 , s表示當前的棋盤大小的一半

//當特殊的棋子在左上角的小棋盤中

if(dr < tr + s && dc < tc + s)

chessBoard(tr , tc , dr , dc , s) ;

else //如果不在左上角小棋盤的話,則把當前該小棋盤的右下角置位一個特殊字符

{

board[tr + s -1][tc + s - 1] = t ; //賦值為編號為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 - 1 && 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()

{

chessBoard(0,0,2 ,3 ,M) ;

for(int i = 0 ; i < M ; i++)

for(int j = 0 ; j < M ; j++)

{

printf("%d " , board[i][j]) ;

if(j == (M-1))

printf("\n") ;

}

getchar() ;

return 0 ;

}

posted on 2010-12-07 20:25 kahn 閱讀(1125) 評論(0) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。


相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

分治法之棋盤分割問題

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

分治法 之 棋盤分割問題

分治法之棋盤分割問題