欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

棋盘覆盖-Java

程序员文章站 2022-05-13 17:14:08
...

来源于算法设计课堂!

问题描述】 2k*2k个方格的一个棋盘,有一个方格残缺

要求:

用三格板覆盖棋盘,

三格板不重叠,

不覆盖残缺方格,

覆盖所有其它方格


  • k>0 时,将2k*2k棋盘分割为 4 2k-1*2k-1子棋盘 ;

  • 特殊方格必位于 4 个较小子棋盘之一中,其余 3 个子棋盘中无特殊方格;

  • 为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘,可以用一个三格板覆盖这 3 个较小棋盘的会合处,从而将原问题转化为 4 较小规模的棋盘覆盖问题

  • 递归地使用这种分割,直至棋盘简化为棋盘 1×1

package com.divide;
public class ChessboardCover {
      static int[][] Board = new int[64][64];
      static int tile = 1;
      public static void main(String[] args) {
            int size  = 4;
            TileBoard(0, 0, 1, 1, size);
            for(int i=0; i< size; i++){
                  for(int j=0; j<size; j++){
                        System.out.print(Board[i][j]+" ");
                  }
                  System.out.println("");
            }
      }
      /**
       * Board[0][0]:表示棋盘中左上角的方格; tile:所使用的三格板数目,初始为1;
       *
       * @param tr
       *            棋盘中左上角方格所在行
       * @param tc
       *            棋盘中左上角方格所在列
       * @param dr
       *            残缺方格所在行
       * @param dc
       *            残缺方格所在列
       * @param size
       *            棋盘的行数或列数 需要的三格板数(size2-1)/3
       */
      public static void TileBoard(int tr, int tc, int dr, int dc, int  size) {
            if (size == 1)
                  return;
            int t = tile++; // 所使用的三格板数目
            int s = size / 2; // 象限大小
            // 覆盖左上象限
            if (dr < tr + s && dc < tc + s) {
                  // 残缺方格位于本象限
                  TileBoard(tr, tc, dr, dc, s);
            } else {// 本象限中没有残缺方格
                        // 把三角格板t放在右下角
                  Board[tr + s - 1][tc + s - 1] = t;
                  // 覆盖其余部分
                  TileBoard(tr, tc, tr + s - 1, tc + s - 1, s);
            }
            // 覆盖右上象限
            if (dr < tr + s && dc >= tc + s) {
                  // 残缺方格位于本象限
                  TileBoard(tr, tc + s, dr, dc, s);
            } else {// 本象限中没有残缺方格
                        // 把三角格板t放在左下角
                  Board[tr + s - 1][tc + s] = t;
                  // 覆盖其余部分
                  TileBoard(tr, tc + s, tr + s - 1, tc + s, s);
            }
            // 覆盖左下象限
            if (dr >= tr + s && dc < tc + s)
                  // 残缺方格位于本象限
                  TileBoard(tr + s, tc, dr, dc, s);
            else { // 把三格板t放在右上角
                  Board[tr + s][tc + s - 1] = t;
                  // 覆盖其余部分
                  TileBoard(tr + s, tc, tr + s, tc + s - 1, s);
            }
            // 覆盖右下象限
            if (dr >= tr + s && dc >= tc + s)
                  // 残缺方格位于本象限
                  TileBoard(tr + s, tc + s, dr, dc, s);
            else { // 把三格板t放在左上角
                  Board[tr + s][tc + s] = t;
                  // 覆盖其余部分
                  TileBoard(tr + s, tc + s, tr + s, tc + s, s);
            }
      }
}

output:

2 2 3 3 
2 0 1 3 
4 1 1 5 
4 4 5 5 

相关标签: 分治 棋盘覆盖