[ARC002D] ボードゲーム
题意翻译
•题目描述
高桥君创造了一个游戏。
格状长盘上最左一列为o的阵地,最右一列为x的阵地。
使用随机排列的棋子o和x。
棋子只能一步一步向前走,不能退和斜着走,被对方吃掉的棋子要从棋盘中拿开,另外不能吃掉自己的棋子。
满足以下条件就是胜利:
a) 把对方的棋子全部吃掉;
b) 1个自己的棋子到达对方的阵地。
o先走,第一回合不能吃对手也不允许取胜!
为了高桥君获胜,请判断o和x哪个赢。
•输入格式:
共H+1行。
第1行是棋盘的高度H(1≦H≦ 2,000)和棋盘的宽度W(3≦W≦2,000)。
接下来的H行每行有W个c[i,j],代表棋盘中每个方格上的棋子,如没有棋子,则由“.”代替。
•输出格式:
输出一行,o或x,代表谁赢。
另外最后要换行。
感谢@MarshalKen 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/arc002/tasks/arc002_4
高橋君は格闘ゲームで友達に負けたのが悔しくてたまらなかったので、今度は自分が勝てるゲームを提案しました。
提案するゲームは格子状のマスでできた盤に向かい合って座り、図の左端 $ 1 $ 列が○の陣地、右端 $ 1 $ 列が×の陣地になります。
ランダムに並べられた○と×の駒を用い、$ 2 $ 人はそれぞれ○か×のどちらかを自分の手駒とします。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_arc002_4/f5fe92cfd753bf30543769fe752daa8f0e6718be.png)図:盤面の例。左端の赤い列が○の陣地,右端の青い列が×の陣地となる。
駒は相手の陣地に向かって$ 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 $ 行で出力せよ。
なお、最後には改行を出力せよ。 ```
<pre class="prettyprint linenums">
3 10
..o.o.xxx.
...o.xo.x.
o.xxo..x..
```
```
<pre class="prettyprint linenums">
o
```
![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_arc002_4/5d05aa92899f9a03b60be38ad72e1ae16f7a41cc.png)
- まず先行の○は $ 3 $ 段目左から $ 5 $ 番目の駒を右に進めます。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_arc002_4/dc602e598a9a6d10414ac62a2bc02f479a763839.png)
- ×の番になりましたが、動かせる駒のうちどの駒を左に進めても、次の○の番に駒を取られてしまいます。
- 取られた後も先程同様、どの駒を動かしても次の○の番に進めた駒を取られてしまいます(図の水色枠にしか移動できない)。
- つまり、最初の $ 1 $ 手目で $ 3 $ 段目左から $ 5 $ 番目の駒を右に進めることで、○の勝利が決定します。
```
<pre class="prettyprint linenums">
3 5
..x..
.o...
...x.
```
```
<pre class="prettyprint linenums">
x
```
- お互い踏み合うことはなく、○は最短で $ 3 $ 手、×は $ 2 $ 手で相手の陣地に到達できるので×の勝利になります。