No.2958 Placing Many L-s
Problem Statement
We call a $1\times 1$ square a cell. An L-mino (L-tetromino) is a figure consisting of $4$ cells, with the shape shown in the image below.
binap has $10^{100}$ L-minoes. Determine whether it is possible to choose some of these L-minoes and, allowing rotations and reflections, tile a rectangle of cells with $N$ rows and $M$ columns without overlaps or gaps.
If it is possible, show one such tiling.
This problem has multiple test cases. Answer for each of the $T$ test cases.
Constraints
・ $1\leq T \leq 500$
・ $1\leq N \leq 500$
・ $1\leq M \leq 500$
・The input consists of integers.
・The sum of $NM$ over all test cases is at most $3\times10^5$.
Input
The input is given from Standard Input in the following format. $Case_i$ represents the $i$-th test case.
$T$ $Case_1$ $Case_2$ $\vdots$ $Case_T$
Each test case is given in the following format.
$N$ $M$
Output
For each test case, in order, output the following.
-
If it is impossible, print
-1followed by a newline. -
If it is possible, first print the number $K$ of L-minoes used for the tiling, followed by a newline.
Then, show a valid tiling in $N$ rows and $M$ columns.
Letting $A_{ij} = k$ when the cell in row $i$ ( $1\leq i\leq N$ ) and column $j$ ( $1\leq j\leq M$ ) is occupied by the $k$-th ( $1\leq k\leq K$ ) L-mino, print
$K$ $A_{11}$ $A_{12}$ $\ldots$ $A_{1M}$ $A_{21}$ $A_{22}$ $\ldots$ $A_{2M}$ $\vdots$ $A_{N1}$ $A_{N2}$ $\ldots$ $A_{NM}$The output must be a valid tiling. That is, for each $k$ ( $1\leq k\leq K$ ), there must be exactly $4$ integer pairs $(i, j)$ such that $A_{ij} = k$, and they must be arranged in an L shape (or a reversed L shape).
If there are multiple possible tilings, you may print any of them.
Sample
Sample 1
Input
1 4 4
Output
4 3 2 2 2 3 2 4 4 3 3 1 4 1 1 1 4
A grid with $4$ rows and $4$ columns can be tiled using $4$ L-minoes.
The tiling in the sample output is shown in the figure below.
L-minoes may be rotated and reflected. The following output is also accepted.
4 1 1 1 2 3 3 1 2 3 4 2 2 3 4 4 4
Sample 2
Input
2 1 1 3 5
Output
-1 -1
A grid with $1$ row and $1$ column cannot be tiled with L-minoes.
A grid with $3$ rows and $5$ columns cannot be tiled with L-minoes.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu