AT_arc040_d.[ARC040D] カクカク塗り

高桥君非常热爱涂地板。地板被分成了一个 $N \times N$ 的网格，其中有些格子上可能存在障碍物（包括可能一个障碍物都没有）。他计划按照以下规则来涂地板：

• 重复以下操作：「将当前所在的格子涂色，然后移动到上下左右相邻的格子之一」。
• 每次移动后需要顺时针旋转 $90$ 度。具体来说，刚刚向上或向下移动完后，接下来的移动方向必须是水平的；刚刚向左或向右移动完后，接下来的移动方向必须是垂直的。
• 不能移动到已经涂过色的格子。
• 不能移出网格边界或移动到障碍物所在的格子。

高桥君已经选择好了起点格子。请判断他是否可以通过合理的路径，将所有没有障碍物的格子全部涂色。注意，初始的移动方向和最终停下的格子没有特别要求。在涂完最后一个格子之后，也不需要再进行移动。

标准输入给出如下数据：

• 第一行包含一个整数 $N\ (2 \leq N \leq 400)$，表示网格的大小。
• 接下来 $N$ 行中每行包含一个长度为 $N$ 的字符串 $S_i$，描述网格的状态。
  • . 表示该格子是可涂色的地板。
  • # 表示该格子有障碍物，不可涂色。
  • s 表示起始格子，高桥君将从此处出发。

保证输入中恰有一个 s，且至少有一个 .。

如果高桥君能将所有没有障碍物的格子全部涂色，输出 POSSIBLE；否则，输出 IMPOSSIBLE。输出结果需要另起一行。

部分分数

题目设有部分分数：

• 对于满足 $N \leq 50$ 的数据集，正确解答可获得 $40$ 分。
• 对于所有测试用例，若能正确解答，可额外获得 $60$ 分。

样例说明 1

通过给定的移动规则，可以如图所示地依次涂色。 

本翻译由 AI 自动生成