溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Java基于分治算法實現的棋盤覆蓋問題。分享給大家供大家參考，具體如下：
在一個2^k * 2^k個方格組成的棋盤中，有一個方格與其它的不同，若使用以下四種L型骨牌覆蓋除這個特殊方格的其它方格，如何覆蓋。四個L型骨牌如下圖：
棋盤中的特殊方格如圖：
實現的基本原理是將2^k * 2^k的棋盤分成四塊2^(k - 1) * 2^(k - 1)的子棋盤，特殊方格一定在其中的一個子棋盤中，如果特殊方格在某一個子棋盤中，繼續遞歸處理這個子棋盤，直到這個子棋盤中只有一個方格為止如果特殊方格不在某一個子棋盤中，將這個子棋盤中的相應的位置設為骨牌號，將這個無特殊方格的了棋盤轉換為有特殊方格的子棋盤，然后再遞歸處理這個子棋盤。以上原理如圖所示：
具體代碼如下：
package demo;
public class Chess {
/*tr表示棋盤左上角行號
tc表示棋盤左上角列號
dr表示特殊棋盤的行號
dc表示特殊棋盤的列號*/
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;
//覆蓋左上角子棋盤
if(dr < tr + s && dc < tc +s) {
//特殊方格在此棋盤中
ChessBoard(tr, tc, dr, dc, s);
}
else {
//此棋盤中無特殊方格，用t號L型骨牌覆蓋右下角
Board[tr + s - 1][tr + 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 {//此棋盤中午特殊方格，用t號L型骨牌覆蓋左下角
Board[tr + s - 1][tc + s] = t;
//覆蓋其余方格
ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
//覆蓋左下角子棋盤
if(dr >= tr + s && dc < tc +s) {
//特殊方格在此棋盤中
ChessBoard(tr + s, tc, dr, dc, s);
}
else {
//此棋盤中無特殊方格，用t號L型骨牌覆蓋右上角
Board[tr + s][tr + s -1] = t;
//覆蓋其余方格
ChessBoard(tr, tc, tr + s , tc + s - 1, s);
}
//覆蓋右下角子棋盤
if(dr >= tr + s && dc >= tc + s) {
//特殊方格在此棋盤中
ChessBoard(tr + s, tc+s, dr, dc, s);
}
else {//此棋盤中無特殊方格，用t號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("億速云測試結果：");
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];
}
運行結果：
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
