問題一覧 > 通常問題

No.2958 Placing Many L-s

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : 👑 binap / テスター : ecottea 👑 hamamu
お気に入りにしたユーザー ProblemId : 10919 / 自分の提出
問題文最終更新日: 2025-01-07 22:39:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 452 (順位表) の他の問題:

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 -1 followed 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もしくは右上の雲マークをクリックしてアカウントを作成してください。