B - マス目と駒 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

H 行 W 列のマス目とチェスの駒が 1 つあります。i (1 ≦ i ≦ H) 行目 j (1 ≦ j ≦ W) 列目のマスを、マス (i,j) と呼ぶことにします。このとき、左上のマスがマス (1,1) で右下のマスがマス (H,W) となっています。また、マス (1,1) 以外のいくつかのマスには障害物が置いてあります。ゲーム好きな兄妹がこのマス目と駒を使って以下のようなゲームをしようとしています。

  • 最初、駒をマス (1,1) に置く。
  • プレイヤーは自分のターンに、駒を 1 つ下か 1 つ右下か 1 つ右のマスのうち障害物のないいずれかのマスに動かさなければならない。つまり、駒がマス (i,j) にあるときは、マス (i+1,j) かマス (i+1,j+1) かマス (i,j+1) のうち障害物のないいずれかのマスに動かさなければならない。ただしこのとき、マス目の外に動かすことはできない。すなわち、i = H のときは下や右下には動かせず、j = W のときは右下や右には動かせない。
  • 交互にターンを繰り返し、自分のターンに駒を動かせなくなったプレイヤーの負けとなる（もう一方のプレイヤーが勝ちとなる）。

2 人ともが勝ちを目指して最適な戦略をとったとき、先手と後手のどちらが勝つでしょうか？

入力

入力は以下の形式で標準入力から与えられる。

H W
S_{1,1}S_{1,2}..S_{1,W}
S_{2,1}S_{2,2}..S_{2,W}
:
S_{H,1}S_{H,2}..S_{H,W}
  • 1 行目には、2 つの整数 H (1 ≦ H ≦ 100), W (1 ≦ W ≦ 100) が空白区切りで与えられる。これは、マス目の行数が H、マス目の列数が W であることを表す。
  • 2 行目からの H 行には、マスの情報が与えられる。このうち i (1 ≦ i ≦ H) 行目には、W 個の文字が与えられる。このうちの j (1 ≦ j ≦ W) 個目の文字 S_{i,j} は、マス (i,j) の情報を表す # または . の文字である。# である場合はマス (i,j) に障害物があることを表し、. である場合はマス (i,j) に障害物がないことを表す。ただし、S_{1,1} は . であることが保証される。

部分点

この問題には部分点が設定されている。

  • H ≦ 4 かつ W ≦ 4 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。

出力

先手が勝つ場合は First を、後手が勝つ場合は Second を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

2 3
.#.
...

出力例1

First

ゲームは、例えば以下のように進行します。o は駒の位置を表しています。

o#.
...
  • 1 ターン目：駒はマス (1,1) にあります。駒を下か右下に動かすことができます。先手は、駒を下に動かしました。
.#.
o..
  • 2 ターン目：駒はマス (2,1) にあります。駒は右にしか動かせません。後手は、駒を右に動かしました。
.#.
.o.
  • 3 ターン目：駒はマス (2,2) にあります。駒は右にしか動かせません。先手は、駒を右に動かしました。
.#.
..o
  • 4 ターン目：駒はマス (2,3) にあります。後手は、駒を動かすことができないため負けとなります。

後手がどのように駒を動かしても、先手は適切な動かし方をすることによって勝つことができるため First を出力します。

入力例2

4 4
....
...#
....
.#..

出力例2

Second

先手がどのように駒を動かしても、後手は適切な動かし方をすることによって勝つことができるため Second を出力します。

入力例3

11 44
............................................
............................................
............................................
.....#.....#####....####.....####....####...
....#.#....#....#..#....#...#....#..#....#..
....#.#....#....#..#.............#..#....#..
...#####...#####...#..........###....####...
...#...#...#....#..#.............#..#....#..
..#.....#..#....#..#....#...#....#..#....#..
..#.....#..#....#...####.....####....####...
............................................

出力例3

Second