棋盘覆盖问题详解（递归）

84 阅读 0 评论 56 点赞

我是靠谱客的博主快乐御姐，最近开发中收集的这篇文章主要介绍棋盘覆盖问题详解（递归），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

棋盘覆盖问题详解（分治，非递归）

（代码由 java 编写）

1.问题描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gU5PZFCa-1647919462709)(file:///C:Users27699AppDataLocalTempksohtmlwpsA0F9.tmp.jpg)]
如图(a)所示，k>0时，有一个2k×2k的棋盘，棋盘中任意位置有一个特殊的方格，要求利用图(b)中的4中L型骨牌覆盖图(a)除特殊方格以外的区域，要求所有区域都要覆盖，并且骨牌不能重叠。

2.解题思路

可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。

这一大堆文字是不是看着就很难受，那就别看了，

假设有一个8*8的棋盘，初始位置（2,7）处有一个棋子，那么如何填充呢，简单点说对于一共就三步

①：把nn的棋盘分成四个n/2 * n/2的小棋盘（例子中也就是分成四个44的棋盘）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V6eCYZzl-1647919462711)(C:Users27699AppDataRoamingTyporatypora-user-imagesimage-20220321115103750.png)]
②:把没有棋子的棋盘块上放上棋子，放到四个棋盘块接壤的角落（本例中也就是（4,4）（5,4）（5,5））
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-deDMCOnn-1647919462711)(C:Users27699AppDataRoamingTyporatypora-user-imagesimage-20220321115431127.png)]

③：再把分出的小棋盘块再次调用上面两步，如果子棋盘长宽=2，那么直接填满
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KluAEpx7-1647919462712)(C:Users27699AppDataRoamingTyporatypora-user-imagesimage-20220321115942321.png)]

听懂了那我就直接上代码

import java.util.Scanner;

public class 棋盘覆盖 {
    public static int i=1;
    public static int QP[][];
    public static void main(String[] args) {
        Scanner scanner=new Scanner (System.in);
        int size = scanner.nextInt ();
        QP=new int[size][size];
        int ZuoBiaoX = scanner.nextInt ()-1;
        int ZuoBiaoY = scanner.nextInt ()-1;
        棋盘覆盖 (0,0,ZuoBiaoX,ZuoBiaoY,size);
        Print (QP);
    }
    public static void 棋盘覆盖(int tx,int ty ,int qx ,int qy,int size){
        int numqxqy=QP[qx][qy];
        if (size==2){
            QP[tx][ty]=i;
            QP[tx+1][ty]=i;
            QP[tx][ty+1]=i;
            QP[tx+1][ty+1]=i;
            QP[qx][qy]=numqxqy;
            i++;
            return;
        }
        else {
            int sizeA=size/2;
            int qx1 = tx+sizeA-1, qx2 = tx+sizeA, qx3 = tx+sizeA-1, qx4 = tx+sizeA, qy1 = ty +sizeA-1, qy2 = ty +sizeA-1, qy3 = ty +sizeA, qy4 = ty +sizeA;
            if (qx<=tx+sizeA-1){
                if (qy<=ty+size-1){
                    qx1=qx;
                    qy1=qy;
                    QP[qx2][qy2]=i;
                    QP[qx3][qy3]=i;
                    QP[qx4][qy4]=i;
                    i++;
                }
                else {
                    qx3=qx;
                    qy3=qy;
                    QP[qx2][qy2]=i;
                    QP[qx1][qy1]=i;
                    QP[qx4][qy4]=i;
                    i++;
                }
            }
            else {
                if (qy<=ty+size-1){
                    qx2=qx;
                    qy2=qy;
                    QP[qx1][qy1]=i;
                    QP[qx3][qy3]=i;
                    QP[qx4][qy4]=i;
                    i++;
                }
                else {
                    qx4=qx;
                    qy4=qy;
                    QP[qx2][qy2]=i;
                    QP[qx3][qy3]=i;
                    QP[qx1][qy1]=i;
                    i++;
                }
            }
            棋盘覆盖 (tx,ty,qx1,qy1,sizeA);
            棋盘覆盖 (tx+sizeA,ty,qx2,qy2,sizeA);
            棋盘覆盖 (tx,ty+sizeA,qx3,qy3,sizeA);
            棋盘覆盖 (tx+sizeA,ty+sizeA,qx4,qy4,sizeA);
        }
    }
    public static void Print(int Num[][]){
        for (int i =0;i<Num.length;i++){
            for (int j =0;j<Num[0].length;j++){
                System.out.print (Num[i][j]+"t");
            }
            System.out.println ();
        }
    }
}

接下来我们解释一下这个代码

首先创建一个全局变量QP，这个二维数组代表着我们的棋盘，二维数组上相同的数字就是我们的L形骨牌，i代表着我们填入期盼的棋子，一般三个一填，因为三个棋子构成一个L型骨牌。

public static int i=1;
public static int QP[][];

获取输入，size就是棋盘大小，ZuoBiaoX就是初始棋子的横坐标，ZuoBiaoY就是初始棋子的纵坐标。为什么要-1呢，在数组中是从0开始，实际我们习惯的计数是从1开始。

Scanner scanner=new Scanner (System.in);
int size = scanner.nextInt ();
QP=new int[size][size];
int ZuoBiaoX = scanner.nextInt ()-1;
int ZuoBiaoY = scanner.nextInt ()-1;

之后调用我们的棋盘覆盖方法，这个方法遵循了刚才说的三步

如果size==2，那就直接给棋盘剩下的三个格子填满i，然后return。

if (size==2){
    QP[tx][ty]=i;
    QP[tx+1][ty]=i;
    QP[tx][ty+1]=i;
    QP[tx+1][ty+1]=i;
    QP[qx][qy]=numqxqy;
    i++;
    return;
}

否则我们把棋盘分成四块，先把中心接壤部分填上L型骨牌

int sizeA=size/2;
int qx1 = tx+sizeA-1, qx2 = tx+sizeA, qx3 = tx+sizeA-1, qx4 = tx+sizeA,
qy1 = ty +sizeA-1, qy2 = ty +sizeA-1, qy3 = ty +sizeA, qy4 = ty +sizeA;
if (qx<=tx+sizeA-1){
    if (qy<=ty+size-1){
        qx1=qx;
        qy1=qy;
        QP[qx2][qy2]=i;
        QP[qx3][qy3]=i;
        QP[qx4][qy4]=i;
        i++;
    }
    else {
        qx3=qx;
        qy3=qy;
        QP[qx2][qy2]=i;
        QP[qx1][qy1]=i;
        QP[qx4][qy4]=i;
        i++;
    }
}
else {
    if (qy<=ty+size-1){
        qx2=qx;
        qy2=qy;
        QP[qx1][qy1]=i;
        QP[qx3][qy3]=i;
        QP[qx4][qy4]=i;
        i++;
    }
    else {
        qx4=qx;
        qy4=qy;
        QP[qx2][qy2]=i;
        QP[qx3][qy3]=i;
        QP[qx1][qy1]=i;
        i++;
    }

然后分别对四个子棋盘递归，也就是16 * 16变四个 8 * 8，然后变16个4 * 4，然后变32个2 * 2，然后这32个2 * 2分别填满。

棋盘覆盖 (tx,ty,qx1,qy1,sizeA);
棋盘覆盖 (tx+sizeA,ty,qx2,qy2,sizeA);
棋盘覆盖 (tx,ty+sizeA,qx3,qy3,sizeA);
棋盘覆盖 (tx+sizeA,ty+sizeA,qx4,qy4,sizeA);

最后调用函数输出

public static void Print(int Num[][]){
    for (int i =0;i<Num.length;i++){
        for (int j =0;j<Num[0].length;j++){
            System.out.print (Num[i][j]+"t");
        }
        System.out.println ();
    }
}

我们来看一下输出，基本上没什么问题，如果看了我的帖子还是没看明白，搞个4*4的棋盘按照上面的几步走一遍就懂了。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mxZxf4Cn-1647919462714)(C:Users27699AppDataRoamingTyporatypora-user-imagesimage-20220321122845470.png)]

3.时间复杂度

这个的时间复杂度还是挺难算的

首先假设来了的2^k*2k的棋盘，设T(k)是覆盖一个2^k * 2^k棋盘所需的时间，则从算法的分治策略可知，T(k)满足如下递归方程：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kBx8XmDb-1647919462714)(file:///C:Users27699AppDataLocalTempksohtmlwps373B.tmp.jpg)]

当k=1就是1*1的棋盘时间复杂度就是1，所以时间复杂度就是4^k

那么在看k*k的棋盘上，时间复杂度就是4^log2k=2k

4.棋盘覆盖非递归算法

Hanoi塔问题是经典的递归算法，按照栈内元素出一进三的思想（具体解题方法可以参考{(27条消息) 汉诺塔Java递归和非递归算法解析_Addam Holmes的博客-CSDN博客}）那么我们的棋盘覆盖问题可以用栈模拟递归吗。

Of course Yes！！！！！！！！

先上代码

import java.util.Scanner;
import java.util.Stack;

public class 棋盘覆盖非递归 {
    public static int i=1;
    public static int QP[][];
    public static void main(String[] args) {
        Scanner scanner=new Scanner (System.in);
        int size = scanner.nextInt ();
        QP=new int[size][size];
        int ZuoBiaoX = scanner.nextInt ()-1;
        int ZuoBiaoY = scanner.nextInt ()-1;
        Stack<QPState> stack = new Stack<> ();
        QPState QP1 = new QPState (0,0,ZuoBiaoX,ZuoBiaoY,size);
        stack.push (QP1);//首元素入栈
        while (stack.size ()>0){
            QPState QPLinShi = stack.pop ();
            if(QPLinShi.size==2){
                int numqxqy=QP[QPLinShi.qx][QPLinShi.qy];
                QP[QPLinShi.tx][QPLinShi.ty]=i;
                QP[QPLinShi.tx+1][QPLinShi.ty]=i;
                QP[QPLinShi.tx][QPLinShi.ty+1]=i;
                QP[QPLinShi.tx+1][QPLinShi.ty+1]=i;
                QP[QPLinShi.qx][QPLinShi.qy]=numqxqy;
                i++;
            }
            else {
                int sizeA=QPLinShi.size/2;
                int qx1 = QPLinShi.tx+sizeA-1;
                int qx2 = QPLinShi.tx+sizeA;
                int qx3 =QPLinShi. tx+sizeA-1;
                int qx4 = QPLinShi.tx+sizeA;
                int qy1 = QPLinShi.ty +sizeA-1;
                int qy2 = QPLinShi.ty +sizeA-1;
                int qy3 = QPLinShi.ty +sizeA;
                int qy4 = QPLinShi.ty +sizeA;
                if (QPLinShi.qx<=QPLinShi.tx+sizeA-1){
                    if (QPLinShi.qy<=QPLinShi.ty+size-1){
                        qx1=QPLinShi.qx;
                        qy1=QPLinShi.qy;
                        QP[qx2][qy2]=i;
                        QP[qx3][qy3]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                    else {
                        qx3=QPLinShi.qx;
                        qy3=QPLinShi.qy;
                        QP[qx2][qy2]=i;
                        QP[qx1][qy1]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                }
                else {
                    if (QPLinShi.qy<=QPLinShi.ty+size-1){
                        qx2=QPLinShi.qx;
                        qy2=QPLinShi.qy;
                        QP[qx1][qy1]=i;
                        QP[qx3][qy3]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                    else {
                        qx4=QPLinShi.qx;
                        qy4=QPLinShi.qy;
                        QP[qx2][qy2]=i;
                        QP[qx3][qy3]=i;
                        QP[qx1][qy1]=i;
                        i++;
                    }
                }
                QPState QPLinShi1 = new QPState (QPLinShi.tx,QPLinShi.ty,qx1,qy1,sizeA);
                QPState QPLinShi2 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty,qx2,qy2,sizeA);
                QPState QPLinShi3 = new QPState (QPLinShi.tx,QPLinShi.ty+sizeA,qx3,qy3,sizeA);
                QPState QPLinShi4 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty+sizeA,qx4,qy4,sizeA);
            }
        }
        for (int i =0;i<QP.length;i++){
            for (int j =0;j<QP[0].length;j++){
                System.out.print (QP[i][j]+"t");
            }
            System.out.println ();
        }
    }
}
class QPState{
    int tx;
    int ty;
    int qx;
    int qy;
    int size;
    public QPState(int tx,int ty ,int qx ,int qy,int size){
        this.tx = tx;
        this.ty = ty;
        this.qx = qx;
        this.qy = qy;
        this.size = size;
    }
}

解释一下这个代码吧，作为一个面向对象语言，学java不会用对象那毫无疑问，学的毫无意义，对象使得java在某些地方变得非常适合写算法。在这个题我们也用到这个方法，要用栈模拟递归，所以我们需要对栈内元素进行某些设定。设置一个类QPState，这个类代表着一个原棋盘的子棋盘。tx，ty是子棋盘左下角在原来的大棋盘上的坐标，qx，qy是子棋盘上已有棋子的坐标，size是子棋盘的大小。

class QPState{
    int tx;
    int ty;
    int qx;
    int qy;
    int size;
    public QPState(int tx,int ty ,int qx ,int qy,int size){
        this.tx = tx;
        this.ty = ty;
        this.qx = qx;
        this.qy = qy;
        this.size = size;
    }
}

继续啊，定义一个栈，获取到的元素封装成刚才定义的QPState，然后入栈

int size = scanner.nextInt ();
QP=new int[size][size];
int ZuoBiaoX = scanner.nextInt ()-1;
int ZuoBiaoY = scanner.nextInt ()-1;
Stack<QPState> stack = new Stack<> ();
QPState QP1 = new QPState (0,0,ZuoBiaoX,ZuoBiaoY,size);

之后当有size=2的子棋盘就输出，否则就按照之前说多的方式一变四。

 while (stack.size ()>0){
            QPState QPLinShi = stack.pop ();
            if(QPLinShi.size==2){
                int numqxqy=QP[QPLinShi.qx][QPLinShi.qy];
                QP[QPLinShi.tx][QPLinShi.ty]=i;
                QP[QPLinShi.tx+1][QPLinShi.ty]=i;
                QP[QPLinShi.tx][QPLinShi.ty+1]=i;
                QP[QPLinShi.tx+1][QPLinShi.ty+1]=i;
                QP[QPLinShi.qx][QPLinShi.qy]=numqxqy;
                i++;
            }
            else {
                int sizeA=QPLinShi.size/2;
                int qx1 = QPLinShi.tx+sizeA-1;
                int qx2 = QPLinShi.tx+sizeA;
                int qx3 =QPLinShi. tx+sizeA-1;
                int qx4 = QPLinShi.tx+sizeA;
                int qy1 = QPLinShi.ty +sizeA-1;
                int qy2 = QPLinShi.ty +sizeA-1;
                int qy3 = QPLinShi.ty +sizeA;
                int qy4 = QPLinShi.ty +sizeA;
                if (QPLinShi.qx<=QPLinShi.tx+sizeA-1){
                    if (QPLinShi.qy<=QPLinShi.ty+size-1){
                        qx1=QPLinShi.qx;
                        qy1=QPLinShi.qy;
                        QP[qx2][qy2]=i;
                        QP[qx3][qy3]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                    else {
                        qx3=QPLinShi.qx;
                        qy3=QPLinShi.qy;
                        QP[qx2][qy2]=i;
                        QP[qx1][qy1]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                }
                else {
                    if (QPLinShi.qy<=QPLinShi.ty+size-1){
                        qx2=QPLinShi.qx;
                        qy2=QPLinShi.qy;
                        QP[qx1][qy1]=i;
                        QP[qx3][qy3]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                    else {
                        qx4=QPLinShi.qx;
                        qy4=QPLinShi.qy;
                        QP[qx2][qy2]=i;
                        QP[qx3][qy3]=i;
                        QP[qx1][qy1]=i;
                        i++;
                    }
                }
                QPState QPLinShi1 = new QPState (QPLinShi.tx,QPLinShi.ty,qx1,qy1,sizeA);
                QPState QPLinShi2 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty,qx2,qy2,sizeA);
                QPState QPLinShi3 = new QPState (QPLinShi.tx,QPLinShi.ty+sizeA,qx3,qy3,sizeA);
                QPState QPLinShi4 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty+sizeA,qx4,qy4,sizeA);
            }
        }

}
            }
            QPState QPLinShi1 = new QPState (QPLinShi.tx,QPLinShi.ty,qx1,qy1,sizeA);
            QPState QPLinShi2 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty,qx2,qy2,sizeA);
            QPState QPLinShi3 = new QPState (QPLinShi.tx,QPLinShi.ty+sizeA,qx3,qy3,sizeA);
            QPState QPLinShi4 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty+sizeA,qx4,qy4,sizeA);
        }
    }


最后输出。
```for (int i =0;i<QP.length;i++){
            for (int j =0;j<QP[0].length;j++){
                System.out.print (QP[i][j]+"t");
            }
            System.out.println ();
        }

最后

以上就是快乐御姐为你收集整理的棋盘覆盖问题详解（递归）的全部内容，希望文章能够帮你解决棋盘覆盖问题详解（递归）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：后端语言基础
浏览次数：84 次浏览
发布日期：2024-01-24 21:05:42
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_okf1_12__23_c2.html

棋盘覆盖问题详解（递归）

概述

棋盘覆盖问题详解（分治，非递归）

1.问题描述

2.解题思路

听懂了那我就直接上代码

接下来我们解释一下这个代码

3.时间复杂度

4.棋盘覆盖非递归算法

Of course Yes！！！！！！！！

最后

评论列表共有 0 条评论

发表评论取消回复

棋盘覆盖问题详解（递归）

概述

棋盘覆盖问题详解（分治，非递归）

1.问题描述

2.解题思路

听懂了那我就直接上代码

接下来我们解释一下这个代码

3.时间复杂度

4.棋盘覆盖非递归算法

Of course Yes！！！！！！！！

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复