Loading... *棋牌覆盖问题（java实现）* **一、问题描述与分析** 问题：在一个$$2^k*2^k$$方格组成的棋盘中，有一个方格与其它的不同，用如下图的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 ![骨牌][1] 分析：用分治法划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k>0时，可将$$2^k*2^k$$的棋盘划分为4个$$2^k-1*2^k-1$$的子棋盘。 ![棋盘][2] 这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处（如图2），从而将原问题转化为4个较小规模的棋盘覆盖问题。 ![子棋盘][3] 递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。 **二、程序实现** ```java import java.util.Scanner; public class ChessBord { static int[][] matrix; static int count; public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("棋盘大小："); while (in.hasNextInt()) { int n = in.nextInt();//棋盘大小 System.out.println("特殊方格位置："); int dr = in.nextInt();//特殊方格的行号 int dc = in.nextInt();//特殊方格的列号 matrix = new int[n][n];//n*n的棋盘大小 count = 0; chessBoard(0, 0, dr, dc, n); for (int[] ii : matrix) { for (int jj : ii) { System.out.printf("%8d", jj); } System.out.println(); } } } /* * n：表示输入矩阵是n*n的方阵 * tr：棋盘左上角方格的行号；tc：棋盘左上角方格的列号 * dr：特殊方格的行号；dc：特殊方格的列号 * size：棋盘的大小是size×size */ public static void chessBoard(int tr, int tc, int dr, int dc, int size) { //如果当前棋盘的尺寸是1,也就是说只有一个方格的时候,返回函数 if (size == 1) return; int curPattern = ++count; //把棋盘从中间平均分为4个部分, size = size / 2; //下面方法分别检索分隔出来的4个部分 //左上部分 if (dr < tr + size && dc < tc + size) { //如果左上部分包含特殊棋盘，那么就直接递归找左上部分,继续把左上部分分隔 chessBoard(tr, tc, dr, dr, size); } else { //如果左上部分不包含特殊棋盘，那么先把左上部分的右下角自定义一个特殊棋盘，然后在递归 matrix[tr + size - 1][tc + size - 1] = curPattern; chessBoard(tr, tc, tr + size - 1, tc + size - 1, size); } //右上部分 if (dr < tr + size && dc >= tc + size) { chessBoard(tr, tc + size, dr, dc, size); } else { matrix[tr + size - 1][tc + size] = curPattern; chessBoard(tr, tc + size, tr + size - 1, tc + size, size); } //左下部分 if (dr >= tr + size && dc < tc + size) { chessBoard(tr + size, tc, dr, dc, size); } else { matrix[tr + size][tc + size - 1] = curPattern; chessBoard(tr + size, tc, tr + size, tc + size - 1, size); } //右下部分 if (dr >= tr + size && dc >= tc + size) { chessBoard(tr + size, tc + size, dr, dc, size); } else { matrix[tr + size][tc + size] = curPattern; chessBoard(tr + size, tc + size, tr + size, tc + size, size); } } } ``` **三、实验结果与分析** 实验结果： ![结果][4] 实验分析： 用递归与分治的思想来解决，也就是把一个大的棋盘分成4个小棋盘，检索填充，然后在把小棋盘继续细分，直到棋盘中只包含一个格子为止。 主干是四个if else循环，也就是说只会执行一个if中的语句，但是会执行3个else中的语句，这3个else中的语句就是构造不可覆盖格子，然后对含有新构造的不可覆盖点的子棋盘来重写进行棋盘覆盖，也就是递归调用棋盘覆盖函数，递归的结束条件就是子棋盘只有一个格子，也就是size = 1，每次调用棋盘覆盖函数，都要进行size = size/2，目的就是把一个大棋盘划分为四个相同大小的子棋盘。 [1]: https://img.xiaowuyike.com/images/2020/07/06/gupd.md.png [2]: https://img.xiaowuyike.com/images/2020/07/06/qipj.md.png [3]: https://img.xiaowuyike.com/images/2020/07/06/erqipj.md.png [4]: https://img.xiaowuyike.com/images/2020/07/06/jpgo.md.png Last modification：July 6th, 2020 at 06:28 pm © 允许规范转载 Support 如果觉得对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
