P - ITF. Puzzle Contest
問題文
$T$ 個のテストケースについて、以下の問題を解いてください。
$H$ 行 $W$ 列のグリッドがあり、上から $r$ 行目、左から $c$ 行目のマスを $(r, c)$ と表します。
次の $3$ 種類の形の壁をいくつか配置することによって、すべての隣接するマスの間にちょうど $1$ 枚の壁が存在するようにしたいです。
使う壁の数を最小化するような配置の方法を $1$ つ求め出力してください。
配置の条件
- すべての隣接するマスの間にちょうど $1$ 枚の壁が存在する
- グリッドの外周や外側に壁がない
- 回転や反転を許容する
- 壁同士が一点で交わることを許容する
ビジュアライザ
問題のビジュアライザをコンテスト開始1時間後ごろに公開予定です。
（13:13 追記）
ビジュアライザの公開時間は未定です。
（13:26 追記）
ビジュアライザを公開しました。以下のURLからアクセスできます。
https://itfpc2024.yu212.dev/
制約
- $2 \leq T \leq 100$
- $2 \leq H, W \leq 100$
- 入力はすべて整数である。
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($300$ 点)
- $2 \leq H, W \leq 5$
- ($300$ 点)
- $2 \leq H \leq 5$
- ($400$ 点)
- $2 \leq H \leq 10$
- ($300$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
$H$ $W$
出力
各テストケースに対する答えを順に以下の形式で出力せよ。
それぞれのテストケースでは、$1$ 行目に使う壁の枚数 $N$ を出力せよ。
回転と反転を含めた $14$ 種類の壁に対し、下記のように番号と基準となる位置を定める。
$i+1$ 行目 $(1 \leq i \leq N)$ では、 $i$ 枚目の壁の種類に対応する番号を $t$、基準となる位置にあるマスを $(x, y)$ とし、x y t をこの順に出力せよ。
壁はどのような順番で出力しても良い。
$N$
$x_1$ $y_1$ $t_1$
$x_2$ $y_2$ $t_2$
$\vdots$
$x_N$ $y_N$ $t_N$
2
3 4
6 7
5
1 2 8
2 1 12
2 3 2
1 4 13
3 2 9
19
1 6 13
2 4 13
3 1 12
5 5 6
6 1 9
1 1 10
1 7 13
2 5 11
3 3 2
4 7 11
5 1 9
5 4 12
2 2 8
3 5 10
4 2 9
1 3 10
4 5 8
5 3 12
6 6 3
最初のテストケースでは、$5$ つの壁によってすべての隣接するマスの間を覆うことができます。
この入力は部分点 $3$ の制約を満たします。
他に、次のような覆い方も条件を満たします。
5
1 1 4
1 3 5
2 1 6
1 4 13
3 2 9
二つ目のテストケースでは、それぞれ、$1$ つ目から $5$ つ目が黄色、$6$ つ目から $12$ つ目が赤、$13$ つ目から $15$ つ目が緑、$16$ つ目から $19$ つ目が青に色付けされた壁の情報を表しています。
$18$ 個以下の壁によってすべての隣接するマスの間を覆うことはできないことが証明できます。
