D - カクカク塗り
Editorial
/
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
イカの高橋君は床を塗るのが大好きです。床は 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
、そうでない場合は IMPOSSIBLE
を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
5 #.... ..s.. ..#.. #.... ##..#
出力例1
POSSIBLE
図のように移動しながら塗れば良いです。
入力例2
5 s.### ..### ###.. #.... #..##
出力例2
IMPOSSIBLE
入力例3
3 ..# .s. #..
出力例3
IMPOSSIBLE