分析
很裸的分治题,建议将样例输出画出来。
把公主视作一个已填的格子,将棋盘四分,在原棋盘中间放一块地毯(分出的四块中哪一块有障碍哪一块就不填)。
然后递归(左下->左上->右下->右上)处理四块小棋盘。
注意边界:当小棋盘为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;
}
大佬%%%%%