GCJ 2019 Round 1A - Pylons
codingcompetitions.withgoogle.com
問題文
私たちの宇宙戦艦のAlgorithmica船は、Pylonsと呼ばれるしつこいロボットによって宇宙の中を追跡されています！
私たちはPylonsを撒くために新しい銀河にテレポートしました。
できるだけ長くこの銀河にいて、次の計画を立てる時間を稼ぎたいです… しかしPylonsに捕まりたくはありません！
この銀河は、縦R行、横C列のマスからなります。i 行目 j 列目 のマスを，マス(i, j) と表します。私たちは好きなマスから始めて、銀河の全てのマスをちょうど1回ずつ訪れるようにワープし続けなければなりません。
つまり、最初のマスを含めて1度来たマスにはもう1度行くことはできません。
Pylonsに私たちが次にどこへ行くかを予測されたくないので、次に移動するマスは今のマスと行や列、対角線が同じマスを選ぶことができません。
つまり、今のマスを (r, c)、次に移動するマスを (r’, c’) として
r = r’
c = c’
r - r’ = c - c’
r + r’ = c + c’
のいずれも成り立ってはいけません。
そのような条件を満たす R × C マスの訪問順はあるでしょうか？
それともPylonsから逃げることは不可能なのでしょうか？
入力
1行目にはテストケースの数 T が与えられ、それ以降の行に T 個のテストケースが与えられます。
各テストケースは 1 行からなり、行の数 R と列の数 C が与えられます。
出力
各テストケースについて、Case #x: y と改行を出力してください。
ここで、x は1から始まるテストケースの番号、 y は問題文の条件を満たすことが可能なら POSSIBLE 、不可能なら IMPOSSIBLE です。
その後、可能であればさらに R × C 行出力してください。
それらの行の i 行目は r_i と c_i からなり、i 回目に訪れるマスが (r_i, c_i) であることを表します。
制約
実行制限時間 : 20秒
メモリ制限 : 1GB
小課題
小課題1 (8点)
T = 16
2 ≤ R ≤ 5
2 ≤ C ≤ 5
小課題2 (23点)
1 ≤ T ≤ 100
2 ≤ R ≤ 20
2 ≤ C ≤ 20
解説
実験してみよう
2 × 2 、2 × 3 、2 × 4 、3 × 2 、3 × 3 、4 × 2 はできない
4 × 4 は複雑
パターン化するには…？
2列・3列を埋めるパターンがあれば良さそう
実装
回転して横長にする
4 × 4 だけ場合分け
2列のとき、3つ進んで2つ戻る(必要な横幅は5)
3列のとき、ぐるぐるする(必要な横幅は4)
残りが奇数列のとき3列、偶数列のとき2列を選べばよい(横長なので大丈夫)
ACコード :
