SnowDawn'Home
0%

分支算法-棋盘覆盖问题

发表于 更新于 分类于

分治算法 - 棋盘覆盖问题

棋盘覆盖问题：有一个残缺的棋盘，由$2^k * 2^k$ 个方格组成，只能用以下四种残缺的方块组成（蓝色的部分表示残缺），成为三格板，两个三格板之间不能重叠，不能覆盖最终图形中的残缺方格。

​ 1号2号3号4号

因为棋盘的组成满足 $2^k*2^k$ ,因此可以将这个问题根据分治的思想，将棋盘不断分为四块，那么每一块都是由$2^{k-1}*2^{k-1}$ 格子组成的，将一个大的棋盘不断分为四份的小棋盘。

为了保证满足覆盖要求和条件，将其中三块的缺口放在中间，这样就可以把缺口覆盖，只留下题目中要求的唯一缺口。

首先考虑k=1的情况，若把某一格放空，方案是唯一的。已知某个正方形和空格，我们按照上下面的办法，可输出方案。首先延中心，将边长为$2^k*2^k$的矩形分成4个边长为$2^{k-1}*2^{k−1}$的矩形。那么空出来的格子，一定位于其中的一个，而另外的三个就可以让它们位于原矩阵中心的那个角空出来

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
 * @Description: 算法分析与设计
 * @Autor: 赵晗
 * @Date: 2022-10-08 21:45:09
 * @LastEditors: 赵晗
 * @LastEditTime: 2022-10-09 22:05:51
 */

#include <iostream>
using namespace std;
int count = 0;
int boardsize = 1;
int Board[8][8];
void Cover(int tr, int tc, int dr, int dc, int size); //填充棋盘的函数
void OutputBoard(int size);
int main()
{
    int x, y;
    int i;
    int k;
    //输入棋盘规模
    cout << "请确认棋盘规模，输入k大小（2k×2k）:" << endl;
    cin >> k;
    for (i = 1; i <= k; i++)
        boardsize *= 2;
    cout << "请输入残缺棋子位置（行号，列号）:" << endl;
    cin >> x >> y;
    Cover(0, 0, x, y, boardsize);
    OutputBoard(boardsize);
}
void Cover(int tr, int tc, int dr, int dc, int size)
{
    if (size < 2)
        return;
    int t = count++;
    int s = size / 2;
    //如果残缺在左上角
    if (dr < tr + s && dc < tc + s)
    {
        Cover(tr, tc, dr, dc, s);
        Board[tr + s - 1][tc + s] = t;
        Board[tr + s][tc + s - 1] = t;
        Board[tr + s][tc + s] = t;
        //返回，填充其他部分
        Cover(tr, tc + s, tr + s - 1, tc + s, s);
        Cover(tr + s, tc, tr + s, tc + s - 1, s);
        Cover(tr + s, tc + s, tr + s, tc + s, s);
    }
    //右上角
    else if (dr < tr + s && dc >= tc + s)
    {
        Cover(tr, tc + s, dr, dc, s);
        Board[tr + s - 1][tc + s - 1] = t;
        Board[tr + s][tc + s - 1] = t;
        Board[tr + s][tc + s] = t;
        //返回，填充其他部分
        Cover(tr, tc, tr + s - 1, tc + s - 1, s);
        Cover(tr + s, tc, tr + s, tc + s - 1, s);
        Cover(tr + s, tc + s, tr + s, tc + s, s);
    }
    else if (dr >= tr + s && dc < tc + s)
    {
        Cover(tr + s, tc, dr, dc, s);
        Board[tr + s - 1][tc + s - 1] = t;
        Board[tr + s - 1][tc + s] = t;
        Board[tr + s][tc + s] = t;
        //返回，填充其他部分
        Cover(tr, tc, tr + s - 1, tc + s - 1, s);
        Cover(tr, tc + s, tr + s - 1, tc + s, s);
        Cover(tr + s, tc + s, tr + s, tc + s, s);
    }
    else if (dr >= tr + s && dc >= tc + s)
    {
        Cover(tr + s, tc + s, dr, dc, s);
        Board[tr + s - 1][tc + s - 1] = t;
        Board[tr + s - 1][tc + s] = t;
        Board[tr + s][tc + s - 1] = t;
        //返回，填充其他部分
        Cover(tr, tc, tr + s - 1, tc + s - 1, s);
        Cover(tr, tc + s, tr + s - 1, tc + s, s);
        Cover(tr + s, tc, tr + s, tc + s - 1, s);
    }
}
void OutputBoard(int size)
{ //输出棋盘的内容
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            cout.width(5);
            cout << Board[i][j];
        }
        cout << endl;
    }
}

分治算法的复杂度分析

分治算法将一个规模为$n$ 的问题分解为k个规模为$\frac{n}{m}$的问题，整个问题的复杂度计算分为三个部分

  • 将问题分解的时间$f(n)$

  • k个小规模问题的时间之和$kT(\frac{n}{m})$

  • 将结果合并的时间$f(n)$

    所以在问题规模$n\neq1$ 的前提下,分治算法的时间复杂度计算公式为
    $$
    T(n) =kT(\frac{n}{m})+f(n)
    $$

    其中，m为将问题分解为了多少个子问题，k是这些子问题中有多少是需要进行计算和解决的，在棋盘覆盖问题中，将问题分为了4份，全部都要解决，所以
    $$
    k = m = 4
    $$

    很简单的可以得到，将这些子问题的结果合并的时间复杂度是$O(1)$

    接下里由master定理可以计算得到
    $$
    T(n) = O(n)
    $$
    时间复杂度求解完成。