(問題 7) NG長方形ゲーム step.final Bash(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
では、実際に解いてみましょう。
まず、あり得る盤面としては 2 ^ 16 通りあります。
このとき、それぞれの盤面で先手が勝てるかどうかについて考えていきます。
まず、自明なものとして、ゲームがすでに終了していればその時点で決着がついています。そのとき、盤面に打たれた点の数が奇数なら先手の負け盤面、偶数なら先手の勝ち盤面となります。
これは問題 5 と同じようにゲームが終了しているかを判定することが出来ます。
ある盤面において、打てる手はまだ点が打たれていない格子点に点を打つことです。
ここで、問題 6 と同様に打てる手に対して結果が決まっていることを仮定します。
(1)盤面に打たれている点が奇数個のとき
次に打つのは後手になります。後手の勝ち = 先手の負けであるため、どの手を打っても先手の勝ち盤面になる場合は先手の勝ち盤面、そうでない場合は先手の負け盤面であることがわかります。
(2)盤面に打たれている点が偶数個のとき
次に打つのは先手になります。問題 6 同様先手が先手の勝ち盤面になる手がある場合には先手の勝ち盤面、そうでない場合は先手の負け盤面になります。
このように打つ手に対して結果がわかれば、先手の勝ち盤面であるか先手の負け盤面であるかはわかります。
ではどのように見ていけばよいのでしょうか？
これはすでに結果が確定しているところからさかのぼって先手の勝ち盤面か先手の負け盤面かを見ていけばよいことがわかります。このような手法を後退解析といいます。
問題
3×3 のグリッドが与えられます。AさんとBさんはグリッドの格子点 (16 個) を以下のように選んでいきます。
Aさんからはじめていき、先に行動が出来なくなった人が負けです。今までの 2 人の選んだ点の座標が与えられるので、最適戦略を行ったときの勝敗を判定してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
S_{1,1} S_{1,2} S_{1,3} S_{1,4}
S_{2,1} S_{2,2} S_{2,3} S_{2,4}
S_{3,1} S_{3,2} S_{3,3} S_{3,4}
S_{4,1} S_{4,2} S_{4,3} S_{4,4}
i (1 ≦ i ≦ 4) 行目には 4 つの整数 S_{i,1} S_{i,2} S_{i,3} S_{i,4} が与えられます。
入力は合計で 4 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。
Aが勝つ場合AをBが勝つ場合はBを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 0 ≦ S_{i,j} ≦ 1 (1 ≦ i ≦ 4, 1 ≦ j ≦ 4)
- 与えられる盤面はまだ決着がついていない盤面である
- 入力例1
-
1 1 0 0
1 0 0 1
1 0 0 0
0 1 0 1
- 出力例1
-
B
- 入力例2
-
1 0 0 1
0 1 0 1
0 0 1 1
0 0 0 1
- 出力例2
-
A
