地毯填补问题

地毯填补问题

题目描述

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

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

输入格式

输入文件共2行。

第一行一个整数k，即给定被填补迷宫的大小为2^k 2^k(0<k<10)；
第二行两个整数x,y，即给出公主所在方格的坐标（x为行坐标，y为列坐标），x和y之间有一个空格隔开。

输出格式

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

样例 #1

样例输入 #1

1
2
3                          
3 3

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

提示

spj 报错代码解释：

  1. c越界；
    2.x,y越界；
    3.(x,y)位置已被覆盖；
    4.(x,y)位置从未被覆盖。

增加样例解释。

样例解释

改不对的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#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.y+n/2){
		if(blank.y<bl.y+n/2){
			dir=1;//空白在第一象限 
		}else{
			dir=2;//空白在第二象限 
		}
	}else{
		if(blank.y<bl.y+n/2){
			dir=3;//空白在第三象限 
		}else{
			dir=4;//空白页在第四象限 
		}
	}
	
	switch(dir){
		case 1:
			cout<<bl.x+n/2<<" "<<bl.y+n/2<<" "<<1<<endl;
			if(n>2){
				split({bl.x,bl.y},n/2,blank);//第一象限
				split({bl.x,bl.y+n/2},n/2,{bl.x+n/2-1,bl.y+n/2});
				split({bl.x+n/2,bl.y},n/2,{bl.x+n/2,bl.y+n/2});
				split({bl.x+n/2,bl.y+n/2},n/2,{bl.x+n/2,bl.y+n/2}); 
			}
			break;
		case 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});
				split({bl.x,bl.y+n/2},n/2,blank);
				split({bl.x+n/2,bl.y},n/2,{bl.x+n/2,bl.y+n/2-1});
				split({bl.x+n/2,bl.y+n/2},n/2,{bl.x+n/2,bl.y+n/2});
			}
			break;
		case 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,bl.y+n/2-1});
				split({bl.x,bl.y},n/2,{bl.x+n/2-1,bl.y+n/2});
				split({bl.x+n/2,bl.y+n/2},n/2,blank);
				split({bl.x+n/2,bl.y+n/2},n/2,{bl.x+n/2,bl.y+n/2});
			}	
			break;
		case 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});
				split({bl.x,bl.y+n/2},n/2,{bl.x+n/2-1,bl.y+n/2});
				split({bl.x,bl.y+n/2-1},n/2,{bl.x+n/2,bl.y+n/2-1});
				split({bl.x+n/2,bl.y+n/1},n/2,blank);
			}
			break;
	}
}
//根据空白所在象限给出其他象限的盖毯子方法
//用递归将问题简单化,比如说4*4的毯子可以拆为4*2*2来计算,
//中间的毯子缺口处指向 空白所在的象限 
 
int main()
{
	int k,x,y;//k是k次方,xy是坐标
	cin>>k; 
	cin>>x>>y;
	int n=1;
	n=n<<k; //将二进制码左移k位,也就相当于2的k次方计算
	split({1,1},n,{x,y});
	//第一个为左上角的坐标,第二个是图的大小,第三个是公主所在位置 
	return 0; 
}