地毯填補(bǔ)問題

題目描述

相傳在一個古老的阿拉伯國家里，有一座宮殿。宮殿里有個四四方方的格子迷宮，國王選擇駙馬的方法非常特殊，也非常簡單：公主就站在其中一個方格子上，只要誰能用地毯將除公主站立的地方外的所有地方蓋上，美麗漂亮聰慧的公主就是他的人了。公主這一個方格不能用地毯蓋住，毯子的形狀有所規(guī)定，只能有四種選擇（如圖）：

并且每一方格只能用一層地毯，迷宮的大小為 $2^k\times 2^k$ 的方形。當(dāng)然，也不能讓公主無限制的在那兒等，對吧？由于你使用的是計(jì)算機(jī)，所以實(shí)現(xiàn)時間為 $1$ 秒。

輸入格式

輸入文件共 $2$ 行。

第一行一個整數(shù) $k$，即給定被填補(bǔ)迷宮的大小為 $2^k\times 2^k$（$0<k\le 10$）；
第二行兩個整數(shù) $x,y$，即給出公主所在方格的坐標(biāo)（$x$ 為行坐標(biāo)，$y$ 為列坐標(biāo)），$x$ 和 $y$ 之間有一個空格隔開。

輸出格式

將迷宮填補(bǔ)完整的方案：每一補(bǔ)（行）為 $xyc$（$x,y$ 為毯子拐角的行坐標(biāo)和列坐標(biāo)，$c$ 為使用毯子的形狀，具體見上面的圖 $1$，毯子形狀分別用 $1,2,3,4$ 表示，$x,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 報錯代碼解釋：

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

$\text{upd?2023.8.19}$：增加樣例解釋。

樣例解釋

大致思路

當(dāng)k=1時，我們可以非常容易得到毯子填補(bǔ)的方案。當(dāng)k=2甚至更大時，我們可以將其劃分為四大塊，但是公主位只有一個，而對于其他沒有公主位的四方格，似乎和原問題形式不一樣。但是我們可以對其加以處理，使其四個子問題都具有相同形式——即，我們可以手動為其他三個沒有公主位的四方格增加新的“公主位”。例如，當(dāng)公主位在左上角時，我們可以將剩余三個四方格的交界處用毯子1來補(bǔ)上，這樣每個四方格都會被分配到一個公主位，稱為特殊的方陣，問題便迎刃而解(如圖所示)。因此我們就可以采用分治的方法去不斷將正方形劃分為4個子正方形，再分別填充，直到小正方形邊長為1時，就是公主位了，不用做任何處理。

8x8的方格里,公主在右上角的格子里,然后在左上角的4x4方格中,選右下角,在左下角的方格中,選右上角,在右下角的方格中,選左上角,組成一個L,現(xiàn)在一個8x8的方格被分為四個4x4的方格,每個4x4的方格中,都有一塊被挖掉的部分,左上角的4*4方格中被挖掉的部分是它右下角組成L的那一塊,右上角的4x4方格中,挖去的是公主的位置,左下角和右下角的方格,挖去的都是L那部分

然后對每個4x4方格,重復(fù)以上操作,直到方格劃分為2*2的,四個格子中有一個被挖去,另外三個自然組成一個L

AC CODE

#include<bits/stdc++.h>
using namespace std;// 正方形左上角坐標(biāo)xx和yy，公主坐標(biāo)x和y，正方形邊長k
void work(int xx,int yy,int x,int y,int k){if(k == 1)  return;k/=2;// 左上角if(x < xx+k && y < yy+k){printf("%d %d %d\n",xx+k,yy+k,1);// 遞歸覆蓋左上角work(xx,yy,x,y,k);// 覆蓋右下角work(xx+k,yy+k,xx+k,yy+k,k);// 覆蓋左下角work(xx+k,yy,xx+k,yy+k-1,k);// 覆蓋右上角work(xx,yy+k,xx+k-1,yy+k,k);}// 右上角else if(x < xx+k && y >= yy+k){printf("%d %d %d\n",xx+k,yy+k-1,2);// 遞歸覆蓋左上角work(xx,yy,xx+k-1,yy+k-1,k);// 覆蓋右下角work(xx+k,yy+k,xx+k,yy+k,k);// 覆蓋左下角work(xx+k,yy,xx+k,yy+k-1,k);// 覆蓋右上角work(xx,yy+k,x,y,k);}// 左下角else if(x >= xx+k && y < yy+k){printf("%d %d %d\n",xx+k-1,yy+k,3);// 遞歸覆蓋左上角work(xx,yy,xx+k-1,yy+k-1,k);// 覆蓋右下角work(xx+k,yy+k,xx+k,yy+k,k);// 覆蓋左下角work(xx+k,yy,x,y,k);// 覆蓋右上角work(xx,yy+k,xx+k-1,yy+k,k);}// 右下角else{printf("%d %d %d\n",xx+k-1,yy+k-1,4);// 遞歸覆蓋左上角work(xx,yy,xx+k-1,yy+k-1,k);// 覆蓋右下角work(xx+k,yy+k,x,y,k);// 覆蓋左下角work(xx+k,yy,xx+k,yy+k-1,k);// 覆蓋右上角work(xx,yy+k,xx+k-1,yy+k,k);}
}int main()
{int x,y,k;cin >> k >> x >> y;work(1,1,x,y,(1 << k));return 0;
}