快捷導(dǎo)航

Java基于分治算法實(shí)現(xiàn)的棋盤覆蓋問題示例

更新時(shí)間：2017年11月23日 10:21:44 作者：萌神哆啦A夢

這篇文章主要介紹了Java基于分治算法實(shí)現(xiàn)的棋盤覆蓋問題,簡單描述了棋盤覆蓋問題,并結(jié)合具體實(shí)例形式分析了java基于分治算法實(shí)現(xiàn)棋盤覆蓋問題的相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Java基于分治算法實(shí)現(xiàn)的棋盤覆蓋問題。分享給大家供大家參考，具體如下：

在一個(gè)2^k * 2^k個(gè)方格組成的棋盤中，有一個(gè)方格與其它的不同，若使用以下四種L型骨牌覆蓋除這個(gè)特殊方格的其它方格，如何覆蓋。四個(gè)L型骨牌如下圖：

棋盤中的特殊方格如圖：

實(shí)現(xiàn)的基本原理是將2^k * 2^k的棋盤分成四塊2^(k - 1) * 2^(k - 1)的子棋盤，特殊方格一定在其中的一個(gè)子棋盤中，如果特殊方格在某一個(gè)子棋盤中，繼續(xù)遞歸處理這個(gè)子棋盤，直到這個(gè)子棋盤中只有一個(gè)方格為止如果特殊方格不在某一個(gè)子棋盤中，將這個(gè)子棋盤中的相應(yīng)的位置設(shè)為骨牌號(hào)，將這個(gè)無特殊方格的了棋盤轉(zhuǎn)換為有特殊方格的子棋盤，然后再遞歸處理這個(gè)子棋盤。以上原理如圖所示：

具體代碼如下：

package demo;
public class Chess {
  /*tr表示棋盤左上角行號(hào)
  tc表示棋盤左上角列號(hào)
  dr表示特殊棋盤的行號(hào)
  dc表示特殊棋盤的列號(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;
    //覆蓋左上角子棋盤
    if(dr < tr + s && dc < tc +s) {
      //特殊方格在此棋盤中
      ChessBoard(tr, tc, dr, dc, s);
    }
    else {
      //此棋盤中無特殊方格，用t號(hào)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號(hào)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號(hào)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號(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("腳本之家測試結(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é)果：