19524번 - Right Angle Painting 다국어

Takahashikun likes to paint floors. There is a floor divided into $N \times N$ grid, and some (possibly zero) cells may contain obstacles.

The information about the grid is given as $N$ strings $S_1, \ldots, S_N$. The $j$-th character of $S_i$ represents the cell $(i, j)$: '.' and 's' represent an empty cell, and '#' represents a cell with obstacles.

There is excatly one cell with 's'. First, Takahashikun enters the cell with 's' and paints this cell. After that, he makes zero or more steps according to the following rule:

• In each step, he moves to one of (vertically or horizontally) adjacent cells and paint it.
• Except for the first step, the direction of movement must be changed by $90$ degrees from the previous step. That is, after he moves horizontally he must move vertically, and vice versa.
• He must not enter already painted cells.
• He must not enter cells with obstacles.
• He must not go out of the grid.

Determine if he can paint all cells without obstacles.

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

Print "POSSIBLE" if he can paint all cells without obstacles. Otherwise print "IMPOSSIBLE".

• $1 \leq N \leq 400$
• $|S_i| = N$
• Each character in $S_i$ is one of '.', '#', or 's'.
• There is exactly one cell with 's'.
• There is at least one cell with '.'.