5 棋盘覆盖（C++思路和代码）分治法练习5

在一个2k∗2k（k为正整数，k<=10，length=2k）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格（其坐标为a,b，分别代表行坐标号和列坐标号），以及有四种L型骨牌（如下图）。求用若干块这种L型骨牌实现除该特殊点棋盘的全覆盖。（本题要求采用分治算法做）

输入格式:

输入三个数，分别是a,b,length.

输出格式:

输出整个棋盘。其中特殊方格填为0，然后铺棋盘的顺序为：先铺四个子棋盘交界的部分，然后递归的对每个子棋盘按照左上，右上，右下，左下的顺时针顺序铺满棋盘。每一块骨牌中三个方格数字相同，按照顺序标号，即第一块骨牌全标为1，第二块骨牌全标为2，...，以此类推。输出的每个数占4个场宽，右对齐。

输入样例:

1 1 4

表示：特殊格子为（1，1），棋盘有4行4列。

输出样例:

   0   2   3   3
   2   2   1   3
   5   1   1   4
   5   5   4   4

提示：先铺三个1，再铺三个2，...，最后铺三个5（即先处理子问题交界的地方，再处理左上，右上，右下，左下的子问题）.

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include 
#include 
#include 

using namespace std;
int box[1500][1500]; // 2的10次幂为1024
int m = 1;  //骨牌编号
void whatf(int x, int y, int a, int b, int length);

int main()
{
    int x, y, length;
    cin >> x >> y >> length;
    x--;y--;

    whatf(x, y, 0, 0, length); //按照提议的函数

    for(int i = 0; i < length; i++) //输出答案
    {
        for(int j = 0; j < length; j++)
            printf("%4d", box[i][j]);
        cout << endl;
    }

    return 0;

}

/*让没有被操作过的方格设为-1
分为几种情况，当只有一个时，就直接是0
当有length = 2时，判断一下哪个被修改过，将其余三个改成m，m再自增
当length > 2时，就将拆分成4个部分，将除了含有小红点的部分都改为m
*/



//x，y为特殊方块的位置，a，b为长和宽的起点，length为正方形尺寸
void whatf(int x, int y, int a, int b, int length)
{
    if(length == 1)
    {
        return;
    }
    int title = m++;
    int size = length/2;
    //如果特殊方块在左上
    if(x < a+size && y < b+size)
    {
        whatf(x, y, a, b, size);
    }
    else //特殊方块不在左上的部分，就将该部分的右下角置为当前骨牌序号
    {
        box[a+size-1][b+size-1] = title; //将右下角置为当前骨牌序号
        whatf(a+size-1, b+size-1, a, b, size);
    }

    //如果特殊方块在右上
    if(x < a+size && y >= b+size)
    {
        whatf(x, y, a, b+size, size);
    }
    else//特殊方块不在右上的部分，就将该部分的左下角置为当前骨牌序号
    {
        box[a+size-1][b+size] = title; //将左下角置为当前骨牌序号
        whatf(a+size-1, b+size, a, b+size, size);
    }

    //如果特殊方块在右下
    if(x >= a+size && y >= b+size)
    {
        whatf(x, y, a+size, b+size, size);
    }
    else
    {
        box[a+size][b+size] = title;
        whatf(a+size, b+size, a+size, b+size, size);
    }

    //如果特殊方块在左下
    if(x >= a+size && y < b+size)
    {
        whatf(x, y, a+size, b, size);
    }
    else
    {
        box[a+size][b+size-1] = title;
        whatf(a+size, b+size-1, a+size, b, size);
    }
}