問題一覧 > 通常問題

No.2958 Placing Many L-s

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 16
作問者 : 👑 binapbinap / テスター : ecotteaecottea hamamuhamamu
4 ProblemId : 10919 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-08 23:27:46

問題文

$1\times 1$ の正方形をマスと呼ぶことにします。Lミノ(Lテトロミノ)は $4$ つのマスから成る図形であり、下の画像に示す形です。

binapくんは $10^{100}$ 個のLミノを持っています。ここからいくつかのLミノを選び、回転や裏返しを許して $N$ 行 $M$ 列のマスからなる長方形の形に重複なくかつ隙間なく敷き詰めることが可能かどうか判別してください。

可能なら敷き詰め方をひとつ示してください。

本題はマルチテストケースです。 $T$ 個のテストケースについて答えてください。

制約

・ $1\leq T \leq 500$

・ $1\leq N \leq 500$

・ $1\leq M \leq 500$

・入力は整数。

・すべてのテストケースについての $NM$ の和が $3\times10^5$ 以下である。

入力

入力は以下の形式で標準入力から与えられます。 $Case_i$ は $i$ 個目のテストケースを表します。

 $T$
 $Case_1$
 $Case_2$
 $\vdots$
 $Case_T$

各テストケースは以下の形式で与えられます。

$N$ $M$

出力

各テストケースについて順に以下を出力してください。

  • 不可能である場合は -1 と出力し改行してください。

  • 可能である場合はまず敷き詰めるのに使うLミノの個数 $K$ を出力し改行してください。

    それに続き可能な敷き詰め方を $N$ 行 $M$ 列で示してください。

    $i$ 行目 ( $1\leq i\leq N$ ) の $j$ 列目 ( $1\leq j\leq M$ ) のマスが $k$ ( $1\leq k\leq K$ ) 番目のLミノによって占有されるとき $A_{ij} = k$ として

    $K$
    $A_{11}$ $A_{12}$ $\ldots$ $A_{1M}$
    $A_{21}$ $A_{22}$ $\ldots$ $A_{2M}$
    $\vdots$
    $A_{N1}$ $A_{N2}$ $\ldots$ $A_{NM}$
    

    を出力してください。可能な敷き詰め方であることを要求します。つまり各 $k$ ( $1\leq k\leq K$ ) について $A_{ij} = k$ なる整数組 $(i, j)$ が丁度 $4$ つ存在し、それらがL字型(あるいは逆L字型)に並ぶことを要求します。

    また敷き詰め方が複数ある場合はそのどれを出力しても構いません。

サンプル

サンプル1
入力
1
4 4
出力
4
3 2 2 2
3 2 4 4
3 3 1 4
1 1 1 4

$4$ 行 $4$ 列のマスは $4$ つのLミノを用いて敷き詰めることが可能です。

出力例の敷き詰め方は下図のような敷き詰め方です。

Lミノは回転と裏返しが許されます。次のように出力しても正解となります。

4
1 1 1 2
3 3 1 2
3 4 2 2
3 4 4 4
サンプル2
入力
2
1 1
3 5
出力
-1
-1

$1$ 行 $1$ 列のマスをLミノで敷き詰めることは不可能です。

$3$ 行 $5$ 列のマスをLミノで敷き詰めることは不可能です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。