本文實(shí)例講述了java基于分治算法實(shí)現(xiàn)的棋盤(pán)覆蓋問(wèn)題。分享給大家供大家參考，具體如下：
在一個(gè)2^k * 2^k個(gè)方格組成的棋盤(pán)中，有一個(gè)方格與其它的不同，若使用以下四種l型骨牌覆蓋除這個(gè)特殊方格的其它方格，如何覆蓋。四個(gè)l型骨牌如下圖：
棋盤(pán)中的特殊方格如圖：
實(shí)現(xiàn)的基本原理是將2^k * 2^k的棋盤(pán)分成四塊2^(k - 1) * 2^(k - 1)的子棋盤(pán)，特殊方格一定在其中的一個(gè)子棋盤(pán)中，如果特殊方格在某一個(gè)子棋盤(pán)中，繼續(xù)遞歸處理這個(gè)子棋盤(pán)，直到這個(gè)子棋盤(pán)中只有一個(gè)方格為止如果特殊方格不在某一個(gè)子棋盤(pán)中，將這個(gè)子棋盤(pán)中的相應(yīng)的位置設(shè)為骨牌號(hào)，將這個(gè)無(wú)特殊方格的了棋盤(pán)轉(zhuǎn)換為有特殊方格的子棋盤(pán)，然后再遞歸處理這個(gè)子棋盤(pán)。以上原理如圖所示：
具體代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
package demo;public class chess { /*tr表示棋盤(pán)左上角行號(hào) tc表示棋盤(pán)左上角列號(hào) dr表示特殊棋盤(pán)的行號(hào) dc表示特殊棋盤(pán)的列號(hào)*/ public static void chessboard(int tr, int tc, int dr, int dc, int size) { if(size == 1) { return; } int t = title ++; int s = size/2; //覆蓋左上角子棋盤(pán) if(dr < tr + s && dc < tc +s) { //特殊方格在此棋盤(pán)中 chessboard(tr, tc, dr, dc, s); } else { //此棋盤(pán)中無(wú)特殊方格，用t號(hào)l型骨牌覆蓋右下角 board[tr + s - 1][tr + s -1] = t; //覆蓋其余方格 chessboard(tr, tc, tr + s - 1, tc + s - 1, s); } //覆蓋右上角子棋盤(pán) if(dr < tr + s && dc >= tc + s) { //特殊方格在此棋盤(pán)中 chessboard(tr, tc+s, dr, dc, s); } else {//此棋盤(pán)中午特殊方格，用t號(hào)l型骨牌覆蓋左下角 board[tr + s - 1][tc + s] = t; //覆蓋其余方格 chessboard(tr, tc + s, tr + s - 1, tc + s, s); } //覆蓋左下角子棋盤(pán) if(dr >= tr + s && dc < tc +s) { //特殊方格在此棋盤(pán)中 chessboard(tr + s, tc, dr, dc, s); } else { //此棋盤(pán)中無(wú)特殊方格，用t號(hào)l型骨牌覆蓋右上角 board[tr + s][tr + s -1] = t; //覆蓋其余方格 chessboard(tr, tc, tr + s , tc + s - 1, s); } //覆蓋右下角子棋盤(pán) if(dr >= tr + s && dc >= tc + s) { //特殊方格在此棋盤(pán)中 chessboard(tr + s, tc+s, dr, dc, s); } else {//此棋盤(pán)中無(wú)特殊方格，用t號(hào)l型骨牌覆蓋左上角 board[tr + s ][tc + s] = t; //覆蓋其余方格 chessboard(tr + s, tc + s, tr + s , tc + s, s); } } @suppresswarnings("static-access") public static void main(string args[]) { system.out.println("服務(wù)器之家測(cè)試結(jié)果："); board[2][2] = 0; chess ch = new chess(); ch.chessboard(0, 0, 2, 2, size); for(int i = 0; i < size; ++ i) { for(int j = 0; j < size; j++) { system.out.print(board[i][j] + " "); } system.out.println(); } } static final int size = 4; static int title = 1; static int board[][] = new int[size][size];} |
運(yùn)行結(jié)果：
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
原文鏈接：http://blog.csdn.net/u014755255/article/details/50531621
