D - ボードゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は格闘ゲームで友達に負けたのが悔しくてたまらなかったので、今度は自分が勝てるゲームを提案しました。
提案するゲームは格子状のマスでできた盤に向かい合って座り、図の左端 1 列が○の陣地、右端 1 列が×の陣地になります。
ランダムに並べられた○と×の駒を用い、2 人はそれぞれ○か×のどちらかを自分の手駒とします。
図：盤面の例。左端の赤い列が○の陣地，右端の青い列が×の陣地となる。
駒は相手の陣地に向かって1 マスずつ前進し、相手に踏まれた駒は盤から取り除きます。
前 1方向にのみ進むことができ、それ以外の斜め・横・後ろには進むことができません。
また、自分の駒を踏むことはできません。

交互に 1 つずつ自分の駒を動かし、相手の駒を全て取り除くか、相手の陣地に自分の駒を 1 つでも置いたら勝利となります。
先行は○のついた駒を持っている人ですが、最初の 1 手目では×を取ることのできない初期配置になっています。
また、初期配置で既にどちらかの勝利条件を満たしていることもありません。

高橋君は必ず勝ちたいので○と×のどちらを手駒にするか悩んでいます。
高橋君が勝てるように、○と×のどちらが勝つか判定しなさい。

入力

入力は以下の形式で標準入力から与えられる。 
H W
c_{11}c_{12}…c_{1W} 
c_{21}c_{22}…c_{2W}
:
:
c_{H1}c_{H2}…c_{HW}
  • 1 行目には、盤の高さを表す整数 H (1 ≦ H ≦ 2,000)、盤の幅を表す整数 W (3 ≦ W ≦ 2,000) が空白を区切りとして与えられる。
  • 2 行目から H 行は、盤の上の駒の配置として各行 W 文字の文字列が与えられる。
  • i 行目の先頭から j 番目の文字である c_{ij}は、., o, xのいずれかで与えらる。
  • c_{ij} が . の場合は何も駒が置かれていないことを、o は○の駒が、x は×の駒が置かれていることを表す。

出力

○が勝つ場合はoを、×が勝つ場合はx を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

3 10
..o.o.xxx.
...o.xo.x.
o.xxo..x..

出力例 1

o
  • まず先行の○は 3 段目左から 5 番目の駒を右に進めます。
  • ×の番になりましたが、動かせる駒のうちどの駒を左に進めても、次の○の番に駒を取られてしまいます。
  • 取られた後も先程同様、どの駒を動かしても次の○の番に進めた駒を取られてしまいます（図の水色枠にしか移動できない）。
  • つまり、最初の 1 手目で 3 段目左から 5 番目の駒を右に進めることで、○の勝利が決定します。

入力例 2

3 5
..x..
.o...
...x.

出力例 2

x
  • お互い踏み合うことはなく、○は最短で 3 手、×は 2 手で相手の陣地に到達できるので×の勝利になります。

Source Name

ARC 002