题目描述

相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：

讯享网

并且每一方格只能用一层地毯，迷宫的大小为 2^k\times 2^k2k×2k 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为 1\mathrm s1s。

输入格式

输入文件共 22 行。

第一行：kk，即给定被填补迷宫的大小为 2^k\times 2^k2k×2k（0\lt k\leq 100<k≤10）；

第二行：x,yx,y，即给出公主所在方格的坐标（xx 为行坐标，yy 为列坐标），xx 和 yy 之间有一个空格隔开。

输出格式

将迷宫填补完整的方案：每一补(行)为x\ y\ cx y c（x,yx,y 为毯子拐角的行坐标和列坐标， cc 为使用毯子的形状，具体见上面的图 11，毯子形状分别用 1,2,3,41,2,3,4 表示，x,y,cx,y,c 之间用一个空格隔开）。

输入输出样例

输入 #1复制

3 3 3 

输出 #1复制

讯享网5 5 1 2 2 4 1 1 4 1 4 3 4 1 2 4 4 1 2 7 3 1 5 4 1 8 3 3 6 3 4 8 1 7 2 2 5 1 4 6 3 2 8 1 2 8 4 1 7 7 1 6 6 1 5 8 3 8 5 2 8 8 1 

说明/提示

事实上感觉四个的形状分别是这样（仅供参考，如果有问题联系 icy）

spj 报错：

1. cc 越界
2. x,yx,y 越界
3. mp[x][y]mp[x][y] 已被占用
4. mp[x][y]mp[x][y] 从未被使用

分析:

这是一道经典的分治题目,用L型的方块去填一个挖掉一块的地砖

先把整个区域划为四个部分,首先判断哪个地方有挖掉的那一块,本题中即点(x,y)所在处,假设点(x,y)在右上角那个部分,那么先用一个L填在另外三个方格的交界处,如下:

8*8的方格里,公主在右上角的格子里,然后在左上角的4*4方格中,选右下角,在左下角的方格中,选右上角,在右下角的方格中,选左上角,组成一个L,现在一个8*8的方格被分为四个4*4的方格,每个4*4的方格中,都有一块被挖掉的部分,左上角的4*4方格中被挖掉的部分是它右下角组成L的那一块,右上角的4*4方格中,挖去的是公主的位置,左下角和右下角的方格,挖去的都是L那部分

然后对每个4*4方格,重复以上操作,直到方格划分为2*2的,四个格子中有一个被挖去,另外三个自然组成一个L

附上AC代码:

#include<iostream> #include<math.h> using namespace std; typedef struct fangge{ int startx; int starty; int length; int coverx; int covery; }fg; int k; int x,y; void devide(fg f); int main() { cin>>k; cin>>x>>y; fg f1; f1.startx=1; f1.starty=1; f1.length=pow(2,k); f1.coverx=x; f1.covery=y; devide(f1); return 0; } void devide(fg f) { int sx=f.startx; int sy=f.starty; int l=f.length; int cx=f.coverx; int cy=f.covery; if(l==2) { if(cx==sx&&cy==sy) { cout<<cx+1<<" "<<cy+1<<" "<<1<<endl; return; } else if(cx==sx&&cy==sy+1) { cout<<cx+1<<" "<<cy-1<<" "<<2<<endl; return; } else if(cx==sx+1&&cy==sy) { cout<<cx-1<<" "<<cy+1<<" "<<3<<endl; return; } else { cout<<cx-1<<" "<<cy-1<<" "<<4<<endl; return; } } int midx,midy; midx=sx+l/2-1; midy=sy+l/2-1; if(cx<=midx&&cy<=midy) { cout<<midx+1<<" "<<midy+1<<" "<<1<<endl; fg f1; f1.startx=sx; f1.starty=sy; f1.length=l/2; f1.coverx=cx; f1.covery=cy; devide(f1); f1.startx=sx; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=midx; f1.covery=midy+1; devide(f1); f1.startx=sx+l/2; f1.starty=sy; f1.length=l/2; f1.coverx=midx+1; f1.covery=midy; devide(f1); f1.startx=sx+l/2; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=midx+1; f1.covery=midy+1; devide(f1); } else if(cx<=midx&&cy>midy) { cout<<midx+1<<" "<<midy<<" "<<2<<endl; fg f1; f1.startx=sx; f1.starty=sy; f1.length=l/2; f1.coverx=midx; f1.covery=midy; devide(f1); f1.startx=sx; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=cx; f1.covery=cy; devide(f1); f1.startx=sx+l/2; f1.starty=sy; f1.length=l/2; f1.coverx=midx+1; f1.covery=midy; devide(f1); f1.startx=sx+l/2; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=midx+1; f1.covery=midy+1; devide(f1); } else if(cx>midx&&cy<=midy) { cout<<midx<<" "<<midy+1<<" "<<3<<endl; fg f1; f1.startx=sx; f1.starty=sy; f1.length=l/2; f1.coverx=midx; f1.covery=midy; devide(f1); f1.startx=sx; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=midx; f1.covery=midy+1; devide(f1); f1.startx=sx+l/2; f1.starty=sy; f1.length=l/2; f1.coverx=cx; f1.covery=cy; devide(f1); f1.startx=sx+l/2; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=midx+1; f1.covery=midy+1; devide(f1); } else { cout<<midx<<" "<<midy<<" "<<4<<endl; fg f1; f1.startx=sx; f1.starty=sy; f1.length=l/2; f1.coverx=midx; f1.covery=midy; devide(f1); f1.startx=sx; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=midx; f1.covery=midy+1; devide(f1); f1.startx=sx+l/2; f1.starty=sy; f1.length=l/2; f1.coverx=midx+1; f1.covery=midy; devide(f1); f1.startx=sx+l/2; f1.starty=sy+l/2; f1.length=l/2; f1.coverx=cx; f1.covery=cy; devide(f1); } }