問題一覧 > 通常問題

No.3598 Queen vs. King

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 43
作問者 : 👑 AngrySadEight / テスター : gomaazarasi ぽえ
ProblemId : 13564 / yukicoder contest 506 裏・クイーンコンテスト (順位表) / 自分の提出
問題文最終更新日: 2026-07-16 08:43:29
yukicoder contest 506 裏・クイーンコンテストの他の問題:

問題文

この問題はインタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う問題）です．

縦 $H$ マス，横 $W$ マスのマス目があります．上から $i(1 \leq i \leq H)$ 番目，左から $j(1 \leq j \leq W)$ 番目のマスを，マス $(i, j)$ と表記します．

最初，マス $(1, 1)$ にクイーンのコマがあり，マス $(H, W)$ にキングのコマがあります．クイーンのコマおよびキングのコマは，マス目の範囲内のマスに自由に出入り可能ですが，範囲外のマスには出入りできません．

これから，Alice と Bob で次に示すゲームを行います．Bob から始めて次に示す操作を Alice と Bob で交互に行います．

  • Alice は，今クイーンのコマが置かれているマスから $1$ 回の移動で到達可能な，キングのコマが置かれていないマスを $1$ つ選び，そのマスにクイーンのコマを移動させる．
  • Bob は，今キングのコマが置かれているマスから $1$ 回の移動で到達可能な，クイーンのコマが置かれておらずクイーンのコマが $1$ 回の移動で到達可能でもないマスを $1$ つ選び，そのマスにキングのコマを移動させる．

Bob の手番においてキングのコマが移動できるマスが存在しない場合，ゲームは終了となります．そうでない場合はゲームは続行します．

あなたのプログラムは Alice として，ジャッジプログラムは Bob として振る舞います．

Alice の目標は，自身の手番 $3$ 回以内でゲームを終了させることです．適切にコマを動かすことで，自身の手番 $3$ 回以内でゲームを終了させてください．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

クイーンのコマの移動方法について（クリックで開く）

クイーンのコマは，$1$ 回の移動において，縦・横・斜めの方向に，通る経路のマスが全て出入り可能である限り自由なマス数進むことができます．ただし，今いるマスにとどまることを $1$ 回の移動とみなすことはできません．厳密には，マス $(i, j)$ にあるクイーンのコマは次のような移動が可能です．

  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j - l)$ はクイーンのコマが出入り可能なマスである．
キングのコマの移動方法について（クリックで開く）

キングのコマは，$1$ 回の移動において，縦・横・斜めの各方向に隣接する，出入り可能なマスに移動できます．より具体的には，マス $(i, j)$ にあるキングのコマは，マス $(i + 1, j), (i + 1, j + 1), (i, j + 1), (i - 1, j + 1), (i - 1, j), (i - 1, j - 1), (i, j - 1), (i + 1, j - 1)$ の各マスに対して，そのマスが出入り可能であれば移動できます．

制約

  • 入力は全て整数
  • $1 \leq T \leq 1000$
  • $3 \leq H, W \leq 100$

入出力

この問題はインタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う問題）です．

あなたのプログラムは Alice として，ジャッジプログラムは Bob として振る舞います．

まず，最初にテストケースの数 $T$ が与えられます．

$T$

各ケースでは最初に $H, W$ が標準入力から与えられます．

$H$ $W$

続いて，Bob の手番では，操作内容が標準入力から与えられます．

$x$ $y$

ここで

  • $(x, y) \neq (0, 0), (x, y) \neq (-1, -1)$ の場合，Bob は自身の手番でキングのコマを $(x, y)$ へ移動させました．この移動は問題文中のルールに従ったものです．
  • $(x, y) = (0, 0)$ の場合，Bob は自身の手番でキングのコマを移動させることができず，ゲームが終了しました．この場合，次のテストケースがあれば続けて処理し，なければプログラムを終了してください．
  • $(x, y) = (-1, -1)$ の場合，Alice の手番で不正な出力（ルールに従わない移動含む）が行われたか，Alice の手番を $3$ 回終えた時点でゲームが終了しなかったことを表します．この場合，既に不正解と判定されていますので，プログラムをただちに終了してください．

また，Alice の手番では，その手番でクイーンのコマを移動させるマス $(x, y)$ を次の形で出力してください．

$x$ $y$

この移動はルールに従ったものである必要があります．

注意点

  • 出力のたびに必ず標準出力を flush してください．そうしない場合，TLE になる可能性があります．
  • 不正な出力が行われた場合，ジャッジの結果は不定です．
  • $(x, y) = (-1, -1)$ が入力として与えられた後に，プログラムをただちに終了しなかった場合，ジャッジの結果は不定です．
  • すべてのテストケースに答えた後は，プログラムをただちに終了してください．そうしなかった場合，ジャッジの結果は不定です．
リアクティブ問題に慣れていない方は，リアクティブ形式の問題についてのまとめ もご確認ください．

サンプル

以下は，正解となる入出力の一連の流れを表したものとなります．

入力出力説明
1 $T = 1$ です．
3 4 $H = 3, W = 4$ です．
2 4 Bob の $1$ 手目です．最初マス $(3, 4)$ にあったキングのコマをマス $(2, 4)$ に移動させました．
2 2 Alice の $1$ 手目です．マス $(1, 1)$ にあったクイーンのコマをマス $(2, 2)$ に移動させます．
クイーンのコマは，キングのコマが $1$ 回の移動で到達可能なマスに動かしてよいことに注意してください．
3 4 Bob の $2$ 手目です．マス $(2, 4)$ にあったキングのコマをマス $(3, 4)$ に移動させました．
1 2 Alice の $2$ 手目です．マス $(2, 2)$ にあったクイーンのコマをマス $(1, 2)$ に移動させます．
2 4 Bob の $3$ 手目です．マス $(3, 4)$ にあったキングのコマをマス $(2, 4)$ に移動させました．
2 3 Alice の $3$ 手目です．マス $(1, 2)$ にあったクイーンのコマをマス $(2, 3)$ に移動させます．
0 0 Bob はキングのコマを動かすことができなくなったので，ゲームが終了しました．
全てのテストケースに対して答えたため，プログラムを終了してください．

不正解となる入出力の一連の流れも以下に示します．

入力出力説明
1 $T = 1$ です．
4 5 $H = 4, W = 5$ です．
3 5 Bob の $1$ 手目です．最初マス $(4, 5)$ にあったキングのコマをマス $(3, 5)$ に移動させました．
2 2 Alice の $1$ 手目です．マス $(1, 1)$ にあったクイーンのコマをマス $(2, 2)$ に移動させます．
3 4 Bob の $2$ 手目です．マス $(3, 5)$ にあったキングのコマをマス $(3, 4)$ に移動させました．
1 2 Alice の $2$ 手目です．マス $(2, 2)$ にあったクイーンのコマをマス $(1, 2)$ に移動させます．
2 4 Bob の $3$ 手目です．マス $(3, 4)$ にあったキングのコマをマス $(2, 4)$ に移動させました．
2 3 Alice の $3$ 手目です．マス $(1, 2)$ にあったクイーンのコマをマス $(2, 3)$ に移動させます．
-1 -1 Alice の $3$ 回目の手番を終えた時点で，Bob はキングのコマをまだ動かすことができるため，不正解となります．
この場合も，プログラムを終了してください．

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