棋牌覆盖问题(java实现)

一、问题描述与分析

问题:在一个$$2^k*2^k$$方格组成的棋盘中,有一个方格与其它的不同,用如下图的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
骨牌
分析:用分治法划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。k>0时,可将$$2^k*2^k$$的棋盘划分为4个$$2^k-1*2^k-1$$的子棋盘。
棋盘
这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘,以便采用递归方法求解,可以用一个L型骨牌覆盖这3个较小棋盘的会合处(如图2),从而将原问题转化为4个较小规模的棋盘覆盖问题。
子棋盘
递归地使用这种划分策略,直至将棋盘分割为1×1的子棋盘。

二、程序实现

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个小棋盘,检索填充,然后在把小棋盘继续细分,直到棋盘中只包含一个格子为止。

主干是四个if else循环,也就是说只会执行一个if中的语句,但是会执行3个else中的语句,这3个else中的语句就是构造不可覆盖格子,然后对含有新构造的不可覆盖点的子棋盘来重写进行棋盘覆盖,也就是递归调用棋盘覆盖函数,递归的结束条件就是子棋盘只有一个格子,也就是size = 1,每次调用棋盘覆盖函数,都要进行size = size/2,目的就是把一个大棋盘划分为四个相同大小的子棋盘。

Last modification:July 6th, 2020 at 06:28 pm
如果觉得对你有用,请随意赞赏