AtCoder Regular Contest 040

D - カクカク塗り


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

問題文

イカの高橋君は床を塗るのが大好きです。床は N \times N のマス目状に区切られており、いくつか(0 個もありうる)のマスには障害物があります。高橋君はこの床を以下のルールで塗ろうと考えています。

  • 「今いるマスの床を塗って、上下左右いずれかの隣のマスに移動する」という行動を繰り返す。
  • 移動するたびに向きを 90 度回転する。すなわち、上または下に移動した直後には右または左に移動し、右または左に移動した直後には上または下に移動する。
  • すでに塗ったマスには移動しない。
  • マス目の外や障害物のあるマスには移動しない。

高橋君は、すでにどのマスからスタートするかを決めています。このとき、高橋君はうまく移動しながら床を塗ることで、障害物のない全てのマスを塗ることが可能でしょうか。ただし、スタート直後の移動方向や最後に塗るマスには特に指定はありません。また、最後のマスを塗った直後には移動する必要はありません。


入力

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

N
S_1
S_2
:
S_N
  • 1 行目には、マス目の 1 辺の個数を表す整数 N (2 ≦ N ≦ 400) が与えられる。

  • 2 行目からの N 行には、マス目の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、長さ N の文字列 S_i が与えられる。このうち j (1 ≦ j ≦ N) 文字目は、i 行目 j 列目のマスの情報を以下のように表す。

    • . の場合:このマスが床であることを表す。
    • # の場合:このマスに障害物があることを表す。
    • s の場合:このマスは床であり、高橋君がスタートしようと決めているマスであることを表す。

    ただし、これらの文字列の中には s がちょうど 1 つ存在すること、. が少なくとも 1 つ以上存在することが保証される。

部分点

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

  • N ≦ 50 を満たすデータセット 1 に正解した場合は、40 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 60 点が与えられる。

出力

全てのマスを塗ることが可能ならば POSSIBLE、そうでない場合は IMPOSSIBLE1 行に出力せよ。出力の末尾に改行を入れること。


入力例1

5
#....
..s..
..#..
#....
##..#

出力例1

POSSIBLE

図のように移動しながら塗れば良いです。

figure

入力例2

5
s.###
..###
###..
#....
#..##

出力例2

IMPOSSIBLE

入力例3

3
..#
.s.
#..

出力例3

IMPOSSIBLE

Submit提出する