AT_iroha2019_day3_d おにごっこ

[problemUrl]: https://atcoder.jp/contests/iroha2019-day3/tasks/iroha2019_day3_d あなたといろはちゃんは、これから $ N\times\ N $ ( $ N $ は奇数)のグリッド上でおにごっこをします。グリッドは上から $ 1,2,\dots,N $ 行、左から $ 1,2,\dots,N $ 列で、いろはちゃんが鬼です。 グリッドは空き地を意味する`.`または障害物を意味する`#`からなり、障害物のマスには $ 2 $ 人とも立ち入ることはできません。 **グリッドの最外辺と、上から奇数行目かつ左から奇数マス目は`#`であること、上から偶数行目かつ左から偶数マス目は`.`であることが保証されます。また、このグリッドでは治安維持のため、`.`には必ず $ 2 $ つ以上の`.`が隣接しています。**(すなわち、行き止まりはありません。) 鬼ごっこは $ 1000 $ ターンからなり、あなたは $ (2,2) $ から、いろはちゃんは $ (N-1,N-1) $ からスタートします。 $ 1 $ ターン毎に $ 2 $ 人は今いるグリッドと辺で隣接する空き地のグリッドに移動するか、今いるグリッドにとどまるかの行動を同時に起こします。二人が同時に同じマスにいる場合、あなたはいろはちゃんに捕まって敗北してしまいます。 あなたは、いろはちゃんと同じ行または列にいて、 $ 2 $ 人の間に障害物がない場合のみにいろはちゃんの位置を観測できます。しかし、いろはちゃんは天才忍者なので常にあなたの位置情報を把握しているかもしれません。厳密には、あるアルゴリズムのもとで動作しています。 いろはちゃんから $ 1000 $ ターン逃げ切ってください。 ### Input & Output Format ゲームの最初に以下の形式でグリッドの情報が与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

N/A

N/A

### 制約 - $ N $ は奇数である - $ 5\ \leq\ N\ \leq\ 9 $ - $ |S_i|\ =\ N(1\ \le\ i\ \le\ N) $ ### 実装上の注意 - この問題は **インタラクティブ形式** である。 - 出力のあと、標準出力を flush しなければならない。 行わなかった場合`TLE`の可能性がある。 - `-2`ないし`-3`を受け取った後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。 ### 解説 [おにごっこ - 解説](https://img.atcoder.jp/iroha2019-day3/editorial-D.pdf) ### Sample Explanation 1 グリッドの例 ``` 9 ######### #.......# #.#.###.# #.....#.# #.###.#.# #...#...# #.#.###.# #.......# ######### ```