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

一、 问题描述

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

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

二、求解策略

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

三、实现

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

1、覆盖算法实现

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

#ifndef PUTTILE_H
#define PUTTILE_H
#include <QVector>
#include <QPoint>class PutTile
{
public:enum TileType{noRBTile,noLBTile,noLTTile,noRTTile};typedef std::pair<QPoint, TileType> pointAndTile;/** @brief 放置三格板* @param rowOfDefeat 残缺方格的行* @param columnOfDefeat 残缺方格的列* @param startRow 当前方格的起始列* @param startColumn 当前方格的起始列* @param size 当前方格的大小*/QVector<pointAndTile> putTile(int rowOfDefeat, int columnOfDefeat,int startRow, int startColumn, int size);
};#endif // PUTTILE_H

// PutTile.cpp
#include "PutTile.h"QVector<PutTile::pointAndTile>
PutTile::putTile(int rowOfDefeat, int columnOfDefeat,int startRow, int startColumn, int size)
{if (size == 1){return QVector<PutTile::pointAndTile>();}int halfSize = size / 2;QVector<PutTile::pointAndTile> 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 <QWidget>
#include <QVector>
#include <QPoint>QT_BEGIN_NAMESPACE
namespace Ui { class DefectedChessboard; }
QT_END_NAMESPACEclass DefectedChessboard : public QWidget
{Q_OBJECTpublic: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<QVector<QRect>> m_vecRects; // 矩阵坐标QVector<PutTile::pointAndTile> m_tile; // 需要绘制的三格板bool m_setDefeat = false; // 是否为设置残缺方格状态QPoint m_defeat = {-1, -1}; // 残缺方格坐标/** @brief 初始化矩形坐标*/void initRects();/** @brief 绘制棋盘* @param painter 绘图对象*/void drawChessboard(QPainter& painter);/** @brief 绘制三格板* @param 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 方阵：