洛谷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;
}