《数据结构、算法与应用 —— C++语言描述》学习笔记 — 分治算法 — 残缺棋盘

《数据结构、算法与应用 —— C++语言描述》学习笔记 — 分治算法 — 残缺棋盘

《数据结构、算法与应用 —— C++语言描述》学习笔记 —分治算法

• 一、 问题描述
• 二、求解策略
• 三、实现
• • 1、覆盖算法实现
  • 2、绘图代码
  • 3、效果

一、 问题描述

残缺棋盘是一个有 2 k ∗ 2 k 2^k*2^k 2k∗2k个方格的棋盘，其中恰有一个方格残缺，如图为两个 k=2 的残缺棋盘：

在残缺期盼中，要求用三格板覆盖残缺棋盘。在覆盖中，任意两个三格板不能重叠，任意一个三格板不能覆盖残缺方格，但三格板必须覆盖其他所有方格。在这种限制条件下，所需的三格板总数为 ( 2 2 k − 1 ) / 3 (2^{2k}-1)/3 (22k−1)/3。四种三格板的形状如图：

二、求解策略

使用分而治之算法，可以很好地解决残缺棋盘问题。把 2 k ∗ 2 k 2^k*2^k 2k∗2k个方格的棋盘实例划分为较小的残缺棋盘实例。一个自然的划分结果是四个 2 k − 1 ∗ 2 k − 1 2^{k-1}*2^{k-1} 2k−1∗2k−1棋盘。然后，我们可以通过在子棋盘的适当位置插入残缺方格使它们转变为残缺棋盘。假设原棋盘的残缺方格位于左上角的子棋盘中，那么其分割结果如图：

三、实现

考虑到棋盘分割结果的呈现，我们使用QT简单做一个分割。绘图代码多来源于我们前面实现的迷宫老鼠应用，我们这里只列出一些关键代码。

1、覆盖算法实现

这个算法还是比较简单的，一种情况实现了其他的都好办。

#ifndef PUTTILE_H
#define PUTTILE_H
#include 
#include 

class PutTile
{
public:
    enum TileType
    {
        noRBTile,
        noLBTile,
        noLTTile,
        noRTTile
    };
    typedef std::pair pointAndTile;
    
    QVector putTile(int rowOfDefeat, int columnOfDefeat,
            int startRow, int startColumn, int size);
};

#endif // PUTTILE_H

// PutTile.cpp
#include "PutTile.h"

QVector
PutTile::putTile(int rowOfDefeat, int columnOfDefeat,
                 int startRow, int startColumn, int size)
{
    if (size == 1)
    {
        return QVector();
    }

    int halfSize = size / 2;
    QVector ret;
    if (rowOfDefeat < startRow + halfSize)
    {
        if (columnOfDefeat < startColumn + halfSize)
        {
            QPoint middleTile(startRow + halfSize - 1, startColumn + halfSize - 1);
            ret.push_back({middleTile, noLTTile});
            ret.append(putTile(rowOfDefeat, columnOfDefeat,
                               startRow, startColumn, halfSize));
            ret.append(putTile(startRow + halfSize - 1, startColumn + halfSize,
                               startRow, startColumn + halfSize, halfSize));
            ret.append(putTile(startRow + halfSize, startColumn + halfSize - 1,
                               startRow + halfSize, startColumn, halfSize));
            ret.append(putTile(startRow + halfSize, startColumn + halfSize,
                               startRow + halfSize, startColumn + halfSize,
                               halfSize));
        }
        else
        {
            QPoint middleTile(startRow + halfSize - 1, startColumn + halfSize - 1);
            ret.push_back({middleTile, noRTTile});
            ret.append(putTile(startRow + halfSize - 1, startColumn + halfSize - 1,
                               startRow, startColumn, halfSize));
            ret.append(putTile(rowOfDefeat, columnOfDefeat,
                               startRow, startColumn + halfSize, halfSize));
            ret.append(putTile(startRow + halfSize, startColumn + halfSize - 1,
                               startRow + halfSize, startColumn, halfSize));
            ret.append(putTile(startRow + halfSize, startColumn + halfSize,
                               startRow + halfSize, startColumn + halfSize,
                               halfSize));
        }
    }
    else
    {
        if (columnOfDefeat < startColumn + halfSize)
        {
            QPoint middleTile(startRow + halfSize - 1, startColumn + halfSize - 1);
            ret.push_back({middleTile, noLBTile});
            ret.append(putTile(startRow + halfSize - 1, startColumn + halfSize - 1,
                               startRow, startColumn, halfSize));
            ret.append(putTile(startRow + halfSize - 1, startColumn + halfSize,
                               startRow, startColumn + halfSize, halfSize));
            ret.append(putTile(rowOfDefeat, columnOfDefeat,
                               startRow + halfSize, startColumn, halfSize));
            ret.append(putTile(startRow + halfSize, startColumn + halfSize,
                               startRow + halfSize, startColumn + halfSize,
                               halfSize));
        }
        else
        {
            QPoint middleTile(startRow + halfSize - 1, startColumn + halfSize - 1);
            ret.push_back({middleTile, noRBTile});
            ret.append(putTile(startRow + halfSize - 1, startColumn + halfSize - 1,
                               startRow, startColumn, halfSize));
            ret.append(putTile(startRow + halfSize - 1, startColumn + halfSize,
                               startRow, startColumn + halfSize, halfSize));
            ret.append(putTile(startRow + halfSize, startColumn + halfSize - 1,
                               startRow + halfSize, startColumn, halfSize));
            ret.append(putTile(rowOfDefeat, columnOfDefeat,
                               startRow + halfSize, startColumn + halfSize,
                               halfSize));
        }
    }

    return ret;
}

2、绘图代码

// DefectedChessboard.h
#ifndef DEFECTEDCHESSBOARD_H
#define DEFECTEDCHESSBOARD_H

#include "PutTile.h"
#include 
#include 
#include 

QT_BEGIN_NAMESPACE
namespace Ui { class DefectedChessboard; }
QT_END_NAMESPACE

class DefectedChessboard : public QWidget
{
    Q_OBJECT

public:
    DefectedChessboard(QWidget *parent = nullptr);
    ~DefectedChessboard();

protected:
    void paintEvent(QPaintEvent*);
    void resizeEvent(QResizeEvent*);
    void mouseReleaseEvent(QMouseEvent* event);

private slots:
    void on_pushButton_showTile_clicked();

    void on_pushButton_setDefect_clicked();

private:
    Ui::DefectedChessboard *ui;
    QVector> m_vecRects; // 矩阵坐标
    QVector m_tile; // 需要绘制的三格板
    bool m_setDefeat = false; // 是否为设置残缺方格状态
    QPoint m_defeat = {-1, -1}; // 残缺方格坐标

    
    void initRects();

    
    void drawChessboard(QPainter& painter);

    
    void drawTile(QPainter& painter);
};
#endif // DEFECTEDCHESSBOARD_H

部分实现：

void DefectedChessboard::mouseReleaseEvent(QMouseEvent *event)
{
    if (!m_setDefeat)
    {
        return;
    }
    m_setDefeat = false;
    ...
}

void DefectedChessboard::on_pushButton_showTile_clicked()
{
    PutTile putFile;
    m_tile = putFile.putTile(m_defeat.x(), m_defeat.y(), 0, 0, CONST_LINE_NUM);
}

void DefectedChessboard::on_pushButton_setDefect_clicked()
{
    m_defeat = {-1, -1};
    m_setDefeat = true;
    update(ui->widget_board->geometry());
}

void DefectedChessboard::drawChessboard(QPainter &painter)
{
    for (int i = 0; i < m_vecRects.size(); ++i)
    {
        for (int j = 0; j < m_vecRects[i].size(); ++j)
        {
            painter.drawRect(m_vecRects[i][j]);
        }
    }

    if (m_defeat.x() != -1)
    {
        painter.fillRect(m_vecRects[m_defeat.x()][m_defeat.y()] - QMargins(CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH), QColor(0, 255, 255));
    }
}

void DefectedChessboard::drawTile(QPainter &painter)
{
    if (m_tileResult.size() == 0)
    {
        return;
    }

    int currentColor = 0;
    for (auto &tile : m_tileResult)
    {
        QRect rectLT = m_vecRects[tile.first.x()][tile.first.y()] - QMargins(CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH);
        QRect rectRT = m_vecRects[tile.first.x()][tile.first.y()+ 1] - QMargins(CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH);
        QRect rectLB = m_vecRects[tile.first.x() + 1][tile.first.y()] - QMargins(CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH);
        QRect rectRB = m_vecRects[tile.first.x() + 1][tile.first.y() + 1] - QMargins(CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH, CONST_LINE_WIDTH);

        currentColor = (currentColor + 24) % QGradient::Preset::NumPresets;
        QGradient::Preset color = (QGradient::Preset)currentColor;
        switch (tile.second)
        {
        case PutTile::noRBTile:
        {
            painter.fillRect(rectLT, color);
            painter.fillRect(rectRT, color);
            painter.fillRect(rectLB, color);
            break;
        }
        case PutTile::noLBTile:
        {
            painter.fillRect(rectLT, color);
            painter.fillRect(rectRT, color);
            painter.fillRect(rectRB, color);
            break;
        }
        case PutTile::noLTTile:
        {
            painter.fillRect(rectRT, color);
            painter.fillRect(rectRB, color);
            painter.fillRect(rectLB, color);
            break;
        }
        case PutTile::noRTTile:
        {
            painter.fillRect(rectLT, color);
            painter.fillRect(rectRB, color);
            painter.fillRect(rectLB, color);
            break;
        }
        }

        update();
    }
}

3、效果

我们这里使用的是 16*16 方阵：