AT_ahc054_a [AHC054A] Treant's Forest
Background
AtCoder王国の南には、通称「迷いの森」と呼ばれる、入るたびに道が変わる不思議な森が広がっている。 この森には、見つけると幸せが訪れるという伝説の花 *Aura Amaryllis*（通称AA）が存在すると言われており、今日もその花を求めて冒険者がやってきた。
迷いの森の真相は、木の魔物「トレント」が木に化けて冒険者を惑わせているというものである。 トレントは迷っている冒険者から魔力を吸い取ることで生命を維持しており、できる限り長い時間、冒険者を森に留まらせたいと考えている。 ただし、冒険者がAAにたどり着けなかった場合、「あの花は存在しなかった」という噂が広まり、それ以降誰も森に来なくなってしまう。 そうなると魔力を得られなくなったトレントたちは、やがて死に絶えてしまうのだ。
また、冒険者は道に迷わないよう、マッピングをしながら森を探索している。 すでにマッピングされた場所にトレントを移動させてしまうと、それが本物の木ではなくトレントであることが冒険者に見破られ、切り倒されてしまう。 このような事態は、何としても避けなければならない。
トレントのボスであるあなたには、冒険者がAAにたどり着くまでの時間ができるだけ長くなるよう、冒険者の動きに応じてトレントたちの配置を適切に調整していくことが求められる。
Description
$ N \times N $ マスの森がある。 左上のマスの座標を $ (0, 0) $ とし、下方向に $ i $ 、右方向に $ j $ マス進んだ位置の座標を $ (i, j) $ とする。 各マスは「空きマス」もしくは「木」のいずれかである。 $ N \times N $ マスの範囲外は木で囲まれている。
マス $ (0, \lfloor \frac{N}{2} \rfloor) $ は森の入口であり、空きマスである。 マス $ (t_i, t_j) $ に伝説の花が咲いており、そこも空きマスである。
伝説の花を求めて、冒険者が森へやってきた。 冒険者は、公開情報である **現在位置** と **確認済みマス**、非公開情報である **目的地** の3つの状態を持つ。 未確認のマスをすべて空きマスであると仮定した森の地図を、**暫定地図** と呼ぶ。
初期状態では、**現在位置** は森の入口、**確認済みマス** はその1マスと $ N\times N $ マスの外部すべて、**目的地** は未定である。 冒険者の行動は毎ターン、以下の順に処理される。
1. **現在位置** に伝説の花がある場合、目的を達成し、行動を終了する。
2. 上下左右それぞれの方向に対し、**現在位置** からその方向に進んだ最初の「木」のマスまで（その木のマスを含む）のすべての未確認マスを **確認済みマス** に追加する。
3. 伝説の花が **確認済みマス** に含まれている場合、**目的地** をそのマスに設定する。
4. **目的地** が未定でなく、**暫定地図** において **目的地** が現在位置から空きマスのみを通って到達不能な場合、**目的地** を未定に戻す。
5. **目的地** が未定であるか、伝説の花以外の **確認済みマス** にある場合、**暫定地図** において、現在位置から空きマスのみを通って到達可能な未確認マスの中から一様ランダムに1つ選び、それを **目的地** に設定する（そのようなマスが存在しない場合、後述するように WA となる）。
6. **暫定地図** において、各マスから空きマスのみを通って **目的地** へ到達する最短距離を計算する。現在位置に隣接する空きマスのうち、**目的地** までの最短距離がより短くなるマスに移動する。そのようなマスが複数ある場合、上下左右の順に優先度をつけ、先に挙げられた方向を選択する。
木の魔物「トレント」のボスであるあなたの目的は、トレントたちに指示を出して冒険者を迷わせ、伝説の花にたどり着くまでのターン数をできるだけ長くすることである。 あなたは毎ターンの開始前に、**確認済みマス** でない任意個の空きマスを選び、それぞれに1体ずつトレントを配置することができる。 トレントを配置したマスは、それ以降「空きマス」ではなく「木」として扱われ、動かすことはできない。
ただし、森の入口から伝説の花まで、空きマスのみを通る経路が必ず1つ以上存在しなければならない。 そのような経路が存在しない場合、解答は WA となる。
### Input & Output Format
まずはじめに、以下の情報が標準入力から与えられる。
> $ N $ $ t_i $ $ t_j $ $ b_{0,0}\cdots b_{0,N-1} $ $ \vdots $ $ b_{N-1,0}\cdots b_{N-1,N-1} $
- 森の縦横の幅 $ N $ は $ 20 \leq N \leq 40 $ を満たす。
- 伝説の花の座標 $ (t_i, t_j) $ は $ 0 \leq t_i, t_j \leq N - 1 $ を満たし、森の入口 $ (0, \lfloor \frac{N}{2} \rfloor) $ とのマンハッタン距離が $ 5 $ 以上であることが保証されている。
- $ b_{i,0} \cdots b_{i,N-1} $ は長さ $ N $ の文字列であり、その $ j $ 文字目 $ b_{i,j} $ は、マス $ (i, j) $ が空きマスであれば `.`、木であれば `T` を表す。
- すべての空きマスは、森の入口 $ (0, \lfloor \frac{N}{2} \rfloor) $ から空きマスのみを通って到達可能であることが保証されている。
次に、以下の処理を繰り返す。 まず、各ターンの開始時に、冒険者の現在位置と、前のターンに新たに確認済みとなったマスが、以下の形式で標準入力から与えられる。
> $ p_i $ $ p_j $ $ n $ $ x_0 $ $ y_0 $ $ \cdots $ $ x_{n-1} $ $ y_{n-1} $
- $ (p_i, p_j) $ は冒険者の現在位置を表す。
- $ n $ は前のターンに新たに確認済みとなったマスの個数であり、 $ (x_k, y_k) $ はその $ k $ 番目のマスの座標である。
- 最初のターンにおいては、 $ (p_i, p_j) = (0, \lfloor \frac{N}{2} \rfloor) $ 、 $ n = 1 $ 、 $ (x_0, y_0) = (0, \lfloor \frac{N}{2} \rfloor) $ である。
$ (p_i, p_j) = (t_i, t_j) $ の場合、冒険者が伝説の花に到達したことを意味し、繰り返しを終了してプログラムも終了する。
そうでない場合、このターンの開始前に新たにトレントを配置するマスの集合を $ (x_0', y_0'), \cdots, (x_{m-1}', y_{m-1}') $ とし、以下の形式で標準出力に出力せよ。
> $ m $ $ x_0' $ $ y_0' $ $ \cdots $ $ x_{m-1}' $ $ y_{m-1}' $
**出力の後には改行をし、更に標準出力を flush しなければならない。** そうしない場合、TLEとなる可能性がある。
**(2025/9/21 15:00 JST 追記)** 解答プログラムのみでなく、ジャッジ側の Tester プログラムの実行時間も実行時間制限に含まれる。 本問題設定では任意のタイミングで解答プログラムを終了することが困難であり、TLE 回避を容易とするため、以下の打ち切り出力の仕様を追加した。
**打ち切り出力**: 新たにトレントを配置するマスの集合を上記の形式で出力する代わりに、`-1` のみからなる行の出力を行い、プログラムを直ちに終了しても良い。 その場合、それ以降は $ m=0 $ の出力が冒険者が伝説の花を見つけるまで続いたものとして処理され、また、Tester がその処理にかかる実行時間は実行時間制限に含まれない。
[例を見る](https://img.atcoder.jp/ahc054/YDAxDRZr_v2.html?lang=ja&seed=0&output=sample)
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 得点
冒険者が森の入口から入り、伝説の花にたどり着くまでにかかった移動回数が、そのテストケースにおける絶対スコアとなる。 絶対スコアは大きいほど良い。
各テストケース毎に、 $ \mathrm{round}(10^9\times \frac{自身の絶対スコア}{全参加者中の最大絶対スコア}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。
最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最大絶対スコア」の計算から除外される。 システムテストは **CE 以外の結果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。
#### テストケース数
- 暫定テスト: 100個
- システムテスト: 3000個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/ahc054/seeds.txt) (sha256=f46e04db0ec8f80d641bbc8e166b1d2f4050a340b356acea1adce1a41a0a7fc8) を公開
#### 相対評価システムについて
暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最大絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。
順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。
#### 実行時間について
実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。
### 入力生成方法
$ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数を $ \mathrm{rand}(L, U) $ とする。
$ N = \mathrm{rand}(20, 40) $ により、森のサイズ $ N $ を生成する。
すべて空きマスの状態から開始し、以下の手順で木の配置を生成する。
まず、木の本数の上限 $ K $ を $ K = \max(1, \mathrm{rand}(0, \lfloor N^2 / 6 \rfloor)) $ により生成する。
森の入口を除いた $ N^2 - 1 $ 個のマスをランダムな順序で $ (i_0, j_0), \cdots, (i_{N^2 - 2}, j_{N^2 - 2}) $ に並べ、各 $ k $ に対して順に以下の処理を行う。
$ (i_k, j_k) $ に木を仮に置いたうえで、すべての空きマスが森の入口から到達可能かを判定する。到達不能な場合は、木を置くのを取りやめる。
置いた木の本数が $ K $ に達した時点で、処理を中断する。
最後に、伝説の花の座標 $ (t_i, t_j) $ を、条件を満たす空きマスの中から一様ランダムに選択する。
### ツール(入力ジェネレータ・ローカルテスタ・ビジュアライザ)
- [Web版](https://img.atcoder.jp/ahc054/YDAxDRZr_v2.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。
- [ローカル版](https://img.atcoder.jp/ahc054/YDAxDRZr_v2.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。
- [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc054/YDAxDRZr_v2_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
#### ツールで用いられる入出力ファイルの仕様
ローカルテスタに与える入力ファイルは以下の形式を用いている。
> $ N $ $ t_i $ $ t_j $ $ b_{0,0}\cdots b_{0,N-1} $ $ \vdots $ $ b_{N-1,0}\cdots b_{N-1,N-1} $ $ q_i^0 $ $ q_j^0 $ $ \vdots $ $ q_i^{N^2-2} $ $ q_j^{N^2-2} $
末尾に追加されている $ (q_i^k, q_j^k) $ は、 $ k $ 回目の目的地を表し、冒険者が目的地を選択する際にはこの順番で見ていき、条件を満たすものが順に選ばれる。 $ q $ は森の入口を除いた $ N^2 - 1 $ 個のマスをランダムな順序で並べることで生成されている。
### サンプルプログラム (Python)
Python による解答例を示す。 このプログラムでは、確認済みとなったマスの管理を行いつつ、トレントは一切配置しない。 ```
N, ti, tj = map(int, input().split())
b = [input() for _ in range(N)]
revealed = [[False] * N for _ in range(N)]
while True:
pi, pj = map(int, input().split())
parts = input().split()
n = int(parts[0])
xy = list(map(int, parts[1:]))
for k in range(n):
x = xy[2 * k]
y = xy[2 * k + 1]
revealed[x][y] = True
if pi == ti and pj == tj:
break
print(0, flush=True)
```