题目描述
相传在一个古老的阿拉伯国家里,有一座宫殿。宫殿里有个四四方方的格子迷宫,国王选择驸马的方法非常特殊,也非常简单:公主就站在其中一个方格子上,只要谁能用地毯将除公主站立的地方外的所有地方盖上,美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住,毯子的形状有所规定,只能有四种选择(如图):
并且每一方格只能用一层地毯,迷宫的大小为 2k×2k 的方形。当然,也不能让公主无限制的在那儿等,对吧?由于你使用的是计算机,所以实现时间为 1s。
输入格式
输入文件共 2 行。
第一行:k,即给定被填补迷宫的大小为 2k×2k(0<k≤10);
第二行:x,y,即给出公主所在方格的坐标(x 为行坐标,y 为列坐标),x 和 y 之间有一个空格隔开。
输出格式
将迷宫填补完整的方案:每一行为 x y c(x,y 为毯子拐角的行坐标和列坐标,c 为使用毯子的形状,具体见上面的图,毯子形状分别用 1,2,3,4 表示,x,y,c 之间用一个空格隔开)。
输入输出样例
输入 #1
输出 #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
|
思路
本题的棋盘是 2k×2k 的,很容易想到分治,把棋盘分成四块,则每块都是 2k−1×2k−1。
然后有公主的那块很容易解决,当 k=1 时铺上一块就可以了;没有公主的那三块,我们可以在中心点附近的三个点处铺上一块,人为的创造一个“公主”。
首先考虑 k=1 的情况,显然一张地毯就能填满。
那么接下来就要扩大到 k=2 了。
这时候,另外三个 2×2 的未上色格子就没有特殊点了,也就没法像一开始的2×2 的格子做。那么可以给每个 2×2 的格子都增加一个特殊点。
只要在四个 2×2 的格子的正中间旁边的 3 个白色格子都填上同一种颜色,然后再分别处理三个 2×2 的格子就可以!
那么再分别处理三个 2×2 格子。
那么同理,当我们扩充到 8×8 的格子时候,也用同样的方法,现将中间点旁边的白点标记为特殊点。
(图片来自于stoorz1023的原创博客)
代码
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
|
#include<iostream> using namespace std; #define dfsUpLeft DFS(originX, originY, originX + (len >> 1) -1, originY + (len >> 1) - 1, len >> 1); #define dfsUpRight DFS(originX, originY+ (len >> 1), originX + (len >> 1) - 1, originY + (len >> 1), len >> 1); #define dfsDownLeft DFS(originX + (len >> 1), originY, originX + (len >> 1), originY + (len >> 1) - 1, len >> 1); #define dfsDownRight DFS(originX + (len >> 1), originY + (len >> 1), originX + (len >> 1), originY + (len >> 1), len >> 1); void DFS(int originX, int originY, int princessX, int princessY, int len) { if (len == 1) { return; } if (princessX - originX < len >> 1) { if (princessY - originY < len >> 1) { printf("%d %d 1\n", originX + (len >> 1), originY + (len >> 1)); DFS(originX, originY, princessX, princessY, len >> 1); dfsUpRight; dfsDownLeft; dfsDownRight; } else { printf("%d %d 2\n", originX + (len >> 1), originY + (len >> 1) - 1, len >> 1); DFS(originX, originY + (len >> 1), princessX, princessY, len >> 1); dfsUpLeft; dfsDownLeft; dfsDownRight; } } else { if (princessY - originY < len >> 1) { printf("%d %d 3\n", originX + (len >> 1) - 1, originY + (len >> 1)); DFS(originX + (len >> 1), originY, princessX, princessY, len >> 1); dfsUpLeft; dfsUpRight; dfsDownRight; } else { printf("%d %d 4\n", originX + (len >> 1) - 1, originY + (len >> 1) - 1); DFS(originX + (len >> 1), originY + (len >> 1), princessX, princessY, len >> 1); dfsUpLeft; dfsUpRight; dfsDownLeft; } } } int main() { int k, x, y; cin >> k >> x >> y; DFS(1, 1, x, y, 1 << k); return 0; }
|