P1228 Carpet Tiling Problem

# Description It is said that in an ancient Arabian country, there was a palace. Inside the palace, there was a square grid maze. The king’s method for choosing a prince consort was very special and simple: the princess stood on one grid cell, and whoever could cover every other cell with carpets, except the one where the princess stood, would win the beautiful, elegant, and intelligent princess. The princess’s cell must not be covered, and the carpet shape is restricted to four options only (see the figure):  Each grid cell may be covered by at most one layer of carpet. The maze is a square of size $2^k\times 2^k$. The time limit is $1$ second.

相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：  并且每一方格只能用一层地毯，迷宫的大小为 $2^k\times 2^k$ 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为 $1$ 秒。

输入文件共 $2$ 行。 第一行一个整数 $k$，即给定被填补迷宫的大小为 $2^k\times 2^k$（$0\lt k\leq 10$）； 第二行两个整数 $x,y$，即给出公主所在方格的坐标（$x$ 为行坐标，$y$ 为列坐标），$x$ 和 $y$ 之间有一个空格隔开。

Output a complete tiling plan: each placement (one line) is $x\ y\ c$ ($x, y$ are the row and column of the carpet’s corner cell, and $c$ is the carpet’s shape; see Figure $1$ above. The four shapes are represented by $1, 2, 3, 4$. Separate $x, y, c$ with a single space).

Explanation of SPJ error codes: 1. $c$ is out of range. 2. $x, y$ are out of range. 3. The position $(x, y)$ has already been covered. 4. The position $(x, y)$ was never covered. $\text{upd 2023.8.19}$: Added sample explanation. ### Sample Explanation  Translated by ChatGPT 5