P1228_地毯填補(bǔ)問題-遞歸構(gòu)造應(yīng)用
#include<bits/stdc++.h>
using namespace std;
struct point{
int x,y;
};
//*****
//*1*2*
//*****
//*3*4*
//*****
//----->y
//|
//|
//x
int split(point bl, int n, point blank){
int dir=0;
if(blank.x<bl.x+n/2){
if(blank.y<bl.y+n/2){
dir=1;//blank cell in sec 1
}else{
dir=2;//sec 2
}
}else{
if(blank.y<bl.y+n/2){
dir=3;//sec 3
}else{
dir=4;//sec 4
}
}
switch(dir){
case 1://blank cell in sec 1
cout<<bl.x+n/2<<" "<<bl.y+n/2<<" "<<1<<endl;
if(n>2){//recusively
split({bl.x,bl.y},n/2,blank);//for sec 1
split({bl.x,bl.y+n/2},n/2,{bl.x+n/2-1,bl.y+n/2});//for sec 2
split({bl.x+n/2,bl.y},n/2,{bl.x+n/2,bl.y+n/2-1});//for sec 3
split({bl.x+n/2,bl.y+n/2},n/2,{bl.x+n/2,bl.y+n/2});//for sec 4
}
break;
case 2://blank cell in sec 2
cout<<bl.x+n/2<<" "<<bl.y+n/2-1<<" "<<2<<endl;
if(n>2){
split({bl.x,bl.y},n/2,{bl.x+n/2-1,bl.y+n/2-1});//for sec 1
split({bl.x,bl.y+n/2},n/2,blank);//for sec 2
split({bl.x+n/2,bl.y},n/2,{bl.x+n/2,bl.y+n/2-1});//for sec 3
split({bl.x+n/2,bl.y+n/2},n/2,{bl.x+n/2,bl.y+n/2});//for sec 4
}
break;
case 3://blank cell in sec 3
cout<<bl.x+n/2-1<<" "<<bl.y+n/2<<" "<<3<<endl;
if(n>2){
split({bl.x,bl.y},n/2,{bl.x+n/2-1,bl.y+n/2-1});//for sec 1
split({bl.x,bl.y+n/2},n/2,{bl.x+n/2-1,bl.y+n/2});//for sec 2
split({bl.x+n/2,bl.y},n/2,blank);//for sec 3
split({bl.x+n/2,bl.y+n/2},n/2,{bl.x+n/2,bl.y+n/2});//for sec 4
}
break;
case 4://blank cell in sec 4
cout<<bl.x+n/2-1<<" "<<bl.y+n/2-1<<" "<<4<<endl;
if(n>2){
split({bl.x,bl.y},n/2,{bl.x+n/2-1,bl.y+n/2-1});//for sec 1
split({bl.x,bl.y+n/2},n/2,{bl.x+n/2-1,bl.y+n/2});//for sec 2
split({bl.x+n/2,bl.y},n/2,{bl.x+n/2,bl.y+n/2-1});//for sec 3
split({bl.x+n/2,bl.y+n/2},n/2,blank);//for sec 4
}
break;
}
return 0;
}
int main(){
int k,x,y;
cin>>k;
cin>>x>>y;
int n=1;
n=n<<k;
split({1,1},n,{x,y});
return 0;
}
