問題一覧 > 通常問題

No.1384 Bishop and Rook

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 21
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
2 ProblemId : 5733 / 出題時の順位表
問題文最終更新日: 2021-02-08 08:52:44

問題文

$\ N \times M\ $のマス目があります。
上から$\ i\ $番目、左から$\ j\ $番目のマスを$\ (i,j)\ $とします。

あなたは現在$\ 1\ $つ石を持っていて、石を好きなマスに置きます。
その後以下の操作$\ 1,2\ $を操作$\ 1\ $から操作$\ 1,2,1,2,\cdots\ $の順で繰り返し、好きなタイミングで操作を終了します。
ただし、操作ができない場合はその時点で操作を終了とします。また、$1$回も操作しなくても良いことに注意してください。

    操作$\ 1 : $今石が置かれているマスと頂点を$\ 1\ $つ共有しているマスに石を移動し、そのマスに石を置く
    (厳密には$\ (i,j)\ $から$\ (i-1,j-1),(i-1,j+1),(i+1,j-1),(i+1,j+1)\ $のいずれかに石を移動させる、ただしマス目の外に出てはいけない)
    操作$\ 2 : $今石が置かれているマスとを$\ 1\ $つ共有しているマスに石を移動し、そのマスに石を置く
    (厳密には$\ (i,j)\ $から$\ (i-1,j),(i,j-1),(i,j+1),(i+1,j)\ $のいずれかに石を移動させる、ただしマス目の外に出てはいけない)

あなたが操作を終了した時点で全てのマスにちょうど$\ 1\ $回ずつ石が置かれたならば、ミツバチ君は喜びます。
最初にマスに石を置いたときも、そのマスに石が置かれたとみなすことに注意してください。

ミツバチ君が喜ぶような石の最初の位置の決め方と操作の仕方はあるでしょうか。
存在する場合は石の位置の決め方と操作の仕方、存在しない場合はその旨を報告してください。
ミツバチ君が喜ぶような石の最初の位置の決め方と操作の仕方が複数ある場合、どれを出力しても正解となります。

$\ T\ $個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

入力の$\ 1\ $行目は以下の通りです。
$T$
そして、$\ T\ $個のテストケースが続きます。これらはそれぞれ以下の形式で与えられます。
$N\ \ M$

  • $1 \leq T \leq 100$
  • $1 \leq N,M \leq 1000$
  • 各入力ファイルについて、与えられるテストケースの$\ N\ $と$\ M\ $の最大値の総和は$\ 1200\ $を超えない。
  • 入力は全て整数

出力

ミツバチ君が喜ぶような石の位置の決め方と操作の仕方が存在しない場合、-1を出力し、改行してください。

そうでない場合、以下のように出力してください。

$Q$
$s\ \ t$
$i_1\ \ j_1$
$i_2\ \ j_2$
$\vdots$
$i_Q\ \ j_Q$

ここで、$\ Q\ $は操作$\ 1,2\ $の合計回数を表します。
また、$\ s,t\ $は石を最初に置くマスが$\ (s,t)\ $であることを、$i_k,j_k(1 \leq k \leq Q)\ $は合計$\ k\ $回操作$\ 1,2\ $を繰り返した後、石が$\ (i_k,j_k)\ $に置かれていることを表します。
よって、以下の制約を満たす出力をしてください。

  • $0 \leq Q$
  • $1 \leq s,i_k \leq N(1 \leq k \leq Q)$
  • $1 \leq t,j_k \leq M(1 \leq k \leq Q)$
  • 出力は全て整数

この場合の出力は合計$\ Q+2\ $行からなります。また、最後に改行してください。

これを$\ T\ $個のテストケース全てについて行ってください。

サンプル

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

$\ 1\ $つ目のテストケースに対する出力は$\ (1,2)\ $に石を置き、操作$\ 1,2,1\ $をこの順で繰り返し石が$\ (2,1),(2,2),(1,1)\ $と移動することを表しています。

以下のような$\ 1\ $つ目のテストケースに対する出力も正解となります。

3
1 1
2 2
2 1
1 2
また、以下のような$\ 1\ $つ目のテストケースに対する出力は不正解となります。
3
1 1
1 2
2 1
2 2
4
1 2
2 1
2 2
1 1
1 2
$\ 1\ $つ目の出力は操作$\ 2\ $から操作しています。$\ 2\ $つ目の出力は$\ (1,2)\ $に$\ 2\ $回石が置かれています。

$\ 2\ $つ目のテストケースについては、どのマスに石を置いても、$\ 1\ $回目の操作で行う操作$\ 1\ $ができないので、操作を終了することになります。
この時、$\ 1\ $つのマスのみに$\ 1\ $回石が置かれたことになり、ミツバチ君は喜びません。

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