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

5 棋盘覆盖(C++思路和代码)分治法练习5,第1张

在一个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);
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/3002912.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-27
下一篇 2022-09-27

发表评论

登录后才能评论

评论列表(0条)

保存