問題文
鱿鱼高桥喜欢粉刷地板。地板是 它分为 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