M_sea

洛谷1228 地毯填补问题
Luogu分析很裸的分治题,建议将样例输出画出来。把公主视作一个已填的格子,将棋盘四分,在原棋盘中间放一块地毯(分...
扫描右侧二维码阅读全文
01
2017/09

洛谷1228 地毯填补问题

Luogu

分析

很裸的分治题,建议将样例输出画出来。

把公主视作一个已填的格子,将棋盘四分,在原棋盘中间放一块地毯(分出的四块中哪一块有障碍哪一块就不填)。
然后递归(左下->左上->右下->右上)处理四块小棋盘。

注意边界:当小棋盘为1*1时直接返回即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
bool q[1025][1025];
void fill(int x,int y,int r,int c) //填地毯
{
    int a=x+r-1,b=y+c-1,xx,yy; //计算坐标
    int hx=(x+a)/2,hy=(y+b)/2; //计算中点
    for (int i=x;i<=a;i++)
        for (int j=y;j<=b;j++)
            if (q[i][j]==1) //找到已填的格子
            {
                xx=i;
                yy=j;
                break;
            }
    if (xx<=hx&&yy<=hy)  //判断已填的格子在哪(这里是左下)
    {
        q[hx+1][hy+1]=1;
        q[hx][hy+1]=1;
        q[hx+1][hy]=1;
        printf("%d %d %d\n",hx+1,hy+1,1);
    }
    else if (xx<=hx&&yy>hy) //(左上)
    {
        q[hx+1][hy+1]=1;
        q[hx+1][hy]=1;
        q[hx][hy]=1;
        printf("%d %d %d\n",hx+1,hy,2);
    }
    else if (xx>hx&&yy>hy) //右上
    {
        q[hx+1][hy]=1;
        q[hx][hy]=1;
        q[hx][hy+1]=1;
        printf("%d %d %d\n",hx,hy,4);
    }
    else if (xx>hx&&yy<=hy) //右下
    {
        q[hx][hy]=1;
        q[hx][hy+1]=1;
        q[hx+1][hy+1]=1;
        printf("%d %d %d\n",hx,hy+1,3);
    }
    if (r==2&&c==2) return; //我这里是边长为2是填完再返回,其实边长为1直接返回也可以
    r/=2; c/=2; //四分的小棋盘的边长
    fill(x,y,r,c); //左下
    fill(x,hy+1,r,c); //左上
    fill(hx+1,y,r,c); //右下
    fill(hx+1,hy+1,r,c); //右上
}
int main()
{
    int k;
    scanf("%d",&k);
    int s=(int)pow(2.0,k*1.0); //计算边长
    int xxx,yyy;
    scanf("%d%d",&xxx,&yyy);
    q[xxx][yyy]=1; //填公主位置
    fill(1,1,s,s); //分治
    return 0;
}
最后修改:2018 年 11 月 30 日 07 : 30 PM

发表评论

1 条评论

  1. ych

    大佬%%%%%