P1228 地毯填补问题【洛谷算法习题】
P1228 地毯填补问题
网页链接
P1228 地毯填补问题
题目描述
相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：
并且每一方格只能用一层地毯，迷宫的大小为2 k × 2 k 2^k\times 2^k2k×2k的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1 11秒。
输入格式
输入文件共2 22行。
第一行一个整数k kk，即给定被填补迷宫的大小为2 k × 2 k 2^k\times 2^k2k×2k（0 < k ≤ 10 0\lt k\leq 100<k≤10）；
第二行两个整数x , y x,yx,y，即给出公主所在方格的坐标（x xx为行坐标，y yy为列坐标），x xx和y yy之间有一个空格隔开。
输出格式
将迷宫填补完整的方案：每一补（行）为x y c x\ y\ cxyc（x , y x,yx,y为毯子拐角的行坐标和列坐标，c cc为使用毯子的形状，具体见上面的图1 11，毯子形状分别用1 , 2 , 3 , 4 1,2,3,41,2,3,4表示，x , y , c x,y,cx,y,c之间用一个空格隔开）。
输入输出样例 #1
输入 #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说明/提示
spj 报错代码解释：
- c cc越界；
- x , y x,yx,y越界；
- ( x , y ) (x,y)(x,y)位置已被覆盖；
- ( x , y ) (x,y)(x,y)位置从未被覆盖。
upd 2023.8.19 \text{upd 2023.8.19}upd 2023.8.19：增加样例解释。
样例解释
解题思路
本题核心是分治递归，解决2 k × 2 k 2^k \times 2^k2k×2k棋盘的L型地毯填补问题。将大棋盘均等划分为左上、右上、左下、右下四个小象限，判断公主所在的特殊点归属象限：对其余三个无特殊点的象限，在棋盘中心交界处铺一块L型地毯，将这三个象限转化为各含一个“虚拟特殊点”的子问题。递归处理每个小象限，直至象限大小为1 × 1 1 \times 11×1终止。递归过程中按规则输出每块地毯的坐标与形状编号，算法时间复杂度为O ( 4 k ) O(4^k)O(4k)，完美适配k ≤ 10 k \le 10k≤10的数据范围，严格满足题目输出要求。
总结
核心逻辑：分治拆解大棋盘为子棋盘，用L型地毯制造虚拟特殊点，递归完成填补。
关键操作：棋盘四等分、特殊点定位、递归填充、地毯信息输出。
效率保障：分治递归逻辑简洁，精准匹配题目规则，输出格式完全符合评测要求。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;#defineuldfs(c+e-1,d+e-1,c,d,e);#defineurdfs(c+e-1,d+e,c,d+e,e);#definedldfs(c+e,d+e-1,c+e,d,e);#definedrdfs(c+e,d+e,c+e,d+e,e);voiddfs(ll a,ll b,ll c,ll d,ll e){if(e==1)return;e>>=1;if(a-c<e&&b-d<e){printf("%lld %lld 1\n",c+e,d+e);dfs(a,b,c,d,e);ur dl dr}if(a-c<e&&b-d>=e){printf("%lld %lld 2\n",c+e,d+e-1);dfs(a,b,c,d+e,e);ul dl dr}if(a-c>=e&&b-d<e){printf("%lld %lld 3\n",c+e-1,d+e);dfs(a,b,c+e,d,e);ul ur dr}if(a-c>=e&&b-d>=e){printf("%lld %lld 4\n",c+e-1,d+e-1);dfs(a,b,c+e,d+e,e);ul ur dl}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll k,x,y;scanf("%lld%lld%lld",&k,&x,&y);dfs(x,y,1,1,1LL<<k);return0;}