递归与分治策略之棋盘覆盖

一、问题描述

二、过程详解

1、棋盘如下图，其中有一特殊方格：16*16

 、

2、第一个分割结果:8*8

3、第二次分割结果:4*4

4、第三次分割结果:2*2

5、第四次分割结果:1*1

6、第一次分割后子棋盘的覆盖效果

三、代码实现

1 package cn.com.zfc.everyday.test;  2   3 import java.util.Scanner;  4   5 /**  6  *   7  * @title ChessboardCoverage  8  * @describe 棋盘覆盖：  9  *           利用分治法，将方形棋盘分成4部分，如果该特殊点在某一部分，我们就去递归他，如果不在某一部分，我们假设一个点为特殊点，同样递归下去，知道全覆盖。 10  *  11  *           左上角的子棋盘（若不存在特殊方格）：则将该子棋盘右下角的那个方格假设为特殊方格； 12  *           右上角的子棋盘（若不存在特殊方格）：则将该子棋盘左下角的那个方格假设为特殊方格； 13  *           左下角的子棋盘（若不存在特殊方格）：则将该子棋盘右上角的那个方格假设为特殊方格； 14  *           右下角的子棋盘（若不存在特殊方格）：则将该子棋盘左上角的那个方格假设为特殊方格； 15  * @author 张富昌 16  * @date 2017年4月9日下午7:36:15 17  */ 18 public class ChessboardCoverage { 19     // 定义棋盘的大小：2^k，需要的骨牌数是：(4^k-1)/3 20     private static int BOARD_SIZE = 8; 21     // 定义一个二维数组用来模拟棋盘 22     private static int[][] board = new int[BOARD_SIZE][BOARD_SIZE]; 23     // 定义一个全局变量，用来记录骨牌的编号 24     private static int tile = 0; 25  26     public static void main(String[] args) { 27         Scanner scanner = new Scanner(System.in); 28         System.out.println("棋盘的大小为：" + BOARD_SIZE); 29         System.out.println("请输入特殊方格所在的行号："); 30         int dr = scanner.nextInt(); 31         System.out.println("请输入特殊方格所在的列号："); 32         int dc = scanner.nextInt(); 33         scanner.close(); 34         // 行号和列号与二位数组的下标相差 1 35         chessBoard(0, 0, dr - 1, dc - 1, BOARD_SIZE); 36         System.out.println("特殊方块在第 " + dr + " 行第 " + dc + "列，覆盖后的棋盘："); 37         // 输出棋盘 38         printBoard(); 39     } 40  41     /** 42      *  43      * @param tr：棋盘左上角方格的行号 44      * @param tc:棋盘左上角方格的列号 45      * @param dr：特殊方格所在的行号 46      * @param dc：特殊方格所在的列号 47      * @param size：当前棋盘的大小 48      */ 49     private static void chessBoard(int tr, int tc, int dr, int dc, int size) { 50         /* 1、当前棋盘的大小是 1 就返回 */ 51         if (size == 1) { 52             return; 53         } 54         int t = tile++; 55         // 分割棋盘，棋盘大小减半 56         int s = size / 2; 57  58         /* 2、覆盖左上角子棋盘 */ 59         if (dr < tr + s && dc < tc + s) { 60             // 特殊方格在此棋盘中 61             chessBoard(tr, tc, dr, dc, s); 62         } else { 63             // 特殊方格不在此棋盘中，用 t 号骨牌覆盖右下角 64             board[tr + s - 1][tc + s - 1] = t; 65             // 覆盖其余方格 66             chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); 67         } 68  69         /* 3、覆盖右上角子棋盘 */ 70         if (dr < tr + s && dc >= tc + s) { 71             // 特殊方格在此棋盘中 72             chessBoard(tr, tc + s, dr, dc, s); 73         } else { 74             // 特殊方格不在此棋盘中，用 t 号骨牌覆盖左下角 75             board[tr + s - 1][tc + s] = t; 76             // 覆盖其余方格 77             chessBoard(tr, tc + s, tr + s - 1, tc + s, s); 78         } 79  80         /* 4、覆盖左下角子棋盘 */ 81         if (dr >= tr + s && dc < tc + s) { 82             // 特殊方格在此棋盘中 83             chessBoard(tr + s, tc, dr, dc, s); 84         } else { 85             // 特殊方格不在此棋盘中，用 t 号骨牌覆盖右上角 86             board[tr + s][tc + s - 1] = t; 87             // 覆盖其余方格 88             chessBoard(tr + s, tc, tr + s, tc + s - 1, s); 89         } 90  91         /* 5、覆盖左下角子棋盘 */ 92         if (dr >= tr + s && dc >= tc + s) { 93             // 特殊方格在此棋盘中 94             chessBoard(tr + s, tc + s, dr, dc, s); 95         } else { 96             // 特殊方格不在此棋盘中，用 t 号骨牌覆盖右上角 97             board[tr + s][tc + s] = t; 98             // 覆盖其余方格 99             chessBoard(tr + s, tc + s, tr + s, tc + s, s);100         }101     }102 103     // 输出棋盘104     private static void printBoard() {105         for (int i = 0; i < BOARD_SIZE; i++) {106             for (int j = 0; j < BOARD_SIZE; j++) {107                 System.out.print(board[i][j] + "\t");108             }109             System.out.println("\n");110         }111     }112 113 }

测试效果：