递归分治 — 例题2.棋盘覆盖

---

一.问题描述

在一个2^k x 2^{k个方格组成的棋盘中,恰有一方格残缺.残缺方格的位置有2}(2k)种。故对任何k≥0,残缺棋盘有2^(2k)种.
在棋盘覆盖问题中,要求用L型骨牌覆盖残缺棋盘上的所有方格且任何2个L型,骨牌不得重叠覆盖.
2^k x 2^{k的棋盘覆盖中,用到的骨牌数为(4}k -1)/3.

二.解题思路

使用分治算法,可以设计解棋盘覆盖问题的一个简捷算法.

当k>0时,将2^k x 2^{k棋盘分割为**4个2}(k-1) x 2^(k-1)子棋盘**, 残缺方格必位于4个子棋盘之一.

其余3个子棋盘中无残缺方格为此将剩余3棋盘转化为残缺棋盘. 用一个L型骨牌覆盖这3个较小棋盘的结合处. 这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1 x 1棋盘.

代码实现中,我们用一个二位整型数组Board表示棋盘,Board[0] [0]是棋盘左上角方格.
tile是算法中的一个全局整型变量,用来表示L型骨牌的编号,其初始值为0.算法的输入参数是:

• tr: 棋盘左上角的行号 tc:棋盘左上角的列号
• dr: 特殊方格所在的行号 dr: 特殊方格所在的列号
• size: size = 2^k, 表示棋盘的规格

代码如下:

#include<bits/stdc++.h>
using namespace std;
int **Board;
int tile=1; //(0 by default)
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    //tr:棋盘左上角方格的行号  tc:棋盘左上角方格列号
    //dr:特殊方格所在的行号    dc:特殊方格所在的列号
    //size:棋盘的行数或列数
    if(size==1) 
    {
        cout<<"size==1,return!"<<endl;
        return;
    }
    int t = tile++, //骨牌编号,每次加1,统一骨牌编号,特殊方格标号为0
    s = size/2;     //象限大小,即分割棋盘,每次规格减半

    //覆盖左上象限
    if(dr<tr+s && dc<tc+s)
        ChessBoard(tr, tc, dr, dc, s);  //特殊方格位于本象限
    else 
    {
        //本象限中没有特殊方格
        Board[tr+s-1][tc+s-1] = t;  //把三格板t放在右下角,将此象限转化为特殊棋盘
        cout<<"此时t:"<<t<<" 填充格坐标位于:("<<tr+s-1<<","<<tc+s-1<<")"<<endl;
        ChessBoard(tr, tc, tr+s-1, tc+s-1, s);  //覆盖其余部分
    }

    //覆盖右上象限
    if(dr<tr+s && dc>=tc+s)
        ChessBoard(tr, tc+s, dr, dc, s);  //特殊方格位于本象限
    else
    {
        //本象限中没有特殊方格
        Board[tr+s-1][tc+s] = t;
        cout<<"此时t:"<<t<<" 填充格坐标位于:("<<tr+s-1<<","<<tc+s<<")"<<endl;
        ChessBoard(tr, tc+s, tr+s-1, tc+s, s);  //覆盖其余部分,棋盘左上角的坐标也要记得更改!
    }
    //覆盖左下象限
    if(dr>=tr+s && dc<tc+s)
        ChessBoard(tr+s, tc, dr, dc, s);
    else
    {
        Board[tr+s][tc+s-1] = t;
        cout<<"此时t:"<<t<<" 填充格坐标位于:("<<tr+s<<","<<tc+s-1<<")"<<endl;
        ChessBoard(tr+s, tc, tr+s, tc+s-1, s);  
    }
    // 覆盖右下象限
    if(dr>=tr+s && dr>=tc+s)
        ChessBoard(tr+s, tc+s, dr, dc, s);
    else
    {
        Board[tr+s][tc+s] = t;
        cout<<"此时t:"<<t<<" 填充格坐标位于:("<<tr+s<<","<<tc+s<<")"<<endl;
        ChessBoard(tr+s, tc+s, tr+s, tc+s, 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;
    }
}

int main()
{
    // size:棋盘的行数或列数
    int size, i;
    cout<<"Lines or Columns of chessBoard: ";
    cin>>size;
    Board = new int*[size];
    for(i=0; i<size; ++i)
    {
        Board[i] = new int[size];
        for(int j=0; j<size; ++j)
            Board[i][j] = 0;
    }

    //dr, dc:特殊方格所在的行号和列号
    int dr, dc;
    cout<<"Line and column NO. of defective grid: ";  //输入特殊格坐标
    cin>>dr>>dc;
    ChessBoard(0, 0, dr, dc, size);
    OutputBoard(size);
    for(int i=0; i<size; ++i)
        delete[] Board[i];
    delete[] Board;
    system("pause");
    return 0;
}

下面图片是自己的课堂作业以及最终用程序跑出来的结果:
测试样例:棋盘大小 8x8, 特殊格坐标(3, 5)
紫色的序号表示填充的顺序,之后通过程序也可以验证.
(好像写错一个,ε=ε=ε=┏(゜ロ゜;)┛)

这里有一个问题,也是上课时老师问过我的一个问题,就是为什么当递归回来的时候,骨牌的编号还是保持一致的呢.
这里面我们知道递归是一直往里走,每一层的骨牌编号+1后保存在系统栈中,当遇到终止条件return回来或者是找遍当前层所有情况return之后,自动弹栈!
这就是为什么可以保证每一层的骨牌编号都是一致的,这个毋庸置疑!

参考毕方明老师《算法设计与分析》课件.

欢迎大家访问个人博客网站—乔治的编程小屋,和我一起为大厂offer努力!