3. 地毯填补
题目ID：1507必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
地毯填补
相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的各自迷宫，国王选择驸马的方法非常特殊，也非常简单：公主站在其中一个方格子上，只要谁能用地毯将除公主站立的地方意外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一方格不能用地毯盖住，毯子的形状有所规定，只能有4种选择，如下图所示：并且每一方格只能用一层地毯，迷宫的大小为 2k2k * 2k2k 的方形。当然，也不能让公主无限制地在那儿等，所以实现时限为1s。
输入格式
输入文件共2行。第一行：k，即给定被填补迷宫的大小为2k2k * 2k2k (0<k≤10)(0<k≤10)；第二行：x y，即给出公主所在方格的坐标（x为行坐标，y为列坐标），x和y之间有一个空格隔开。
输出格式
输出文件包括将地毯填补完整的方案，每一行为x y c（x,y为毯子拐角的行坐标和列坐标，c为使用毯子的形状，具体见上面的图，毯子形状分别用1、2、3、4表示，x、y、c之间用一个空格隔开）。输出时按X坐标优先,X坐标相同再按Y坐标从小到大排序.
样例
Input 1
3 3 3
Output 1
1 1 4 1 4 2 1 5 4 1 8 2 2 2 4 2 7 2 3 6 2 4 1 3 4 4 1 4 8 1 5 1 4 5 5 1 5 8 2 6 3 3 6 6 1 7 2 3 7 7 1 8 1 3 8 4 1 8 5 3 8 8 1
数据范围
迷宫的大小为（2^k）^2的方形，k（0<k<=10）
\LARGE 特别提示！！！这里的2和3是反的！！！各位dalao们请自行把2和3换一下OvO
代码:
#include<bits/stdc++.h>
using namespace std;
long long n,x,y;
int k;
int res[2005][2005];
long long power(int k){
long long ans=1;
for(int i=1;i<=k;i++){
ans*=2;
}
return ans;
}
void solve(long long x,long long y,long long s,long long t,long long len){
if(len==1){
return;
}
int l=len/2;
if(x-s<=l-1&&y-t<=l-1){
res[s+l][t+l]=1;
solve(x,y,s,t,l);
solve(s+l-1,t+l,s,t+l,l);
solve(s+l,t+l-1,s+l,t,l);
solve(s+l,t+l,s+l,t+l,l);
}
else if(x-s<=l-1&&y-t>l-1){
res[s+l][t+l-1]=3;
solve(x,y,s,t+l,l);
solve(s+l-1,t+l-1,s,t,l);
solve(s+l,t+l-1,s+l,t,l);
solve(s+l,t+l,s+l,t+l,l);
}
else if(x-s>l-1&&y-t<l-1){
res[s+l-1][t+l]=2;
solve(x,y,s+l,t,l);
solve(s+l-1,t+l-1,s,t,l);
solve(s+l-1,t+l,s,t+l,l);
solve(s+l,t+l,s+l,t+l,l);
}
else{
res[s+l-1][t+l-1]=4;
solve(x,y,s+l,t+l,l);
solve(s+l-1,t+l-1,s,t,l);
solve(s+l-1,t+l,s,t+l,l);
solve(s+l,t+l-1,s+l,t,l);
}
}
int main(){
cin>>k;
cin>>x>>y;
n=power(k);
solve(x,y,1,1,n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(res[i][j]!=0){
cout<<i<<" "<<j<<" "<<res[i][j]<<endl;
}
}
}
return 0;
}
