/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
これはインタラクティブな問題です。
問題文
あなたといろはちゃんは、これから 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 ターン逃げ切ってください。
制約
- N は奇数である
- 5 \leq N \leq 9
- |S_i| = N(1 \le i \le N)
入出力
ゲームの最初に以下の形式でグリッドの情報が与えられる。
N S_1 S_2 \vdots S_N
まず、各ターンの開始時にあなたは
U(上に 1 マス移動)D(下に 1 マス移動)L(左に 1 マス移動)R(右に 1 マス移動)-(動かない)
#マスに入った場合WAとなります。
次に、ジャッジはいろはちゃんの行動を行い、その結果を出力します。ここで、いろはちゃんはあなたの行動を受けて行動しうることに留意してください。
ジャッジからのフィードバックは以下の種類に分けられます。
x\ y\ (xとyは正の整数)
この場合、あなたからいろはちゃんが見えて、いろはちゃんが x 行 y 列にいることを表します。(5/2 13:44追記)
-1 -1
この場合、あなたからいろはちゃんが見えないことを表します。
-2 -2
この場合、あなたがいろはちゃんに捕まった、もしくは出力に不備があったことを表します。この返答を受け取った場合、あなたは直ちにプログラムを終了してください。
-3 -3
この場合、あなたが 1000 ターン逃げ切ったことを表します。 この返答はちょうど 1000 ターン目にのみ得られます。この返答を受け取った場合も、あなたは直ちにプログラムを終了してください。
実装上の注意
- この問題は インタラクティブ形式 である。
- 出力のあと、標準出力を flush しなければならない。 行わなかった場合
TLEの可能性がある。 -2ないし-3を受け取った後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
入力例
グリッドの例
7 ####### #.....# #.#.#.# #.....# #.#.#.# #.....# #######
9 ######### #.......# #.#.###.# #.....#.# #.###.#.# #...#...# #.#.###.# #.......# #########