P16876 [GKS 2022 #B] Hamiltonian Tour

Hamilton is a Canadian city near Toronto, and a nice place to take a walking tour. In this problem, Hamilton is represented by a grid of unit cells with $2R$ rows and $2C$ columns, where each cell is either empty (represented by `*`) or contains a building (represented by `#`). The cell on the $i$-th row and $j$-th column is represented by $A_{i,j}$ where $1 \le i \le 2R$ and $1 \le j \le 2C$. It is not possible to enter cells containing buildings and you can only move to an adjacent cell that shares a side with the current cell (not just a corner). The grid is such that if it is divided evenly into $2 \times 2$ blocks of unit cells, then in each of those blocks, either all four cells are empty, or all four cells are occupied by a building. Let us represent the block formed by $A_{2i-1,2j-1}$, $A_{2i-1,2j}$, $A_{2i,2j-1}$, and $A_{2i,2j}$ cells as $B_{i,j}$ where $1 \le i \le R$ and $1 \le j \le C$. Grace is a tourist in Hamilton and wants to visit all the empty cells in Hamilton. Grace is currently in cell $A_{1,1}$. Visiting the same cell twice could be boring for her. Hence, Grace wants to visit each of the empty cells exactly once and finally end in cell $A_{1,1}$. Can you help Grace by providing a string (consisting of directional moves $\{N, E, S, W\}$ representing the unit moves to the north, east, south, or west respectively) which Grace can follow to visit every empty cell once and end again in $A_{1,1}$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains $2$ integers $R$ and $C$. The next $R$ lines of each test case contains $C$ characters each. The $j$-th character on the $i$-th of these lines represents the block $B_{i,j}$ formed by the following $4$ cells: $A_{2i-1,2j-1}$, $A_{2i-1,2j}$, $A_{2i,2j-1}$, and $A_{2i,2j}$. If $B_{i,j} = \#$, all $4$ of the cells in $B_{i,j}$ are occupied by a building. Otherwise, if $B_{i,j} = \ast$, all $4$ of the cells in $B_{i,j}$ are empty.

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the answer to the problem as follows. If there is no solution to the problem, $y$ should be `IMPOSSIBLE`. Otherwise, $y$ should be a sequence of characters from the set $\{N, E, S, W\}$, representing the unit moves (to the north, east, south, or west respectively) in a valid route, starting from $A_{1,1}$, as described in the statement above. Note that your last move should take you to $A_{1,1}$; this move does not count as visiting the same cell twice. If there are multiple valid solutions, you may output any one of them.

The sample output displays one set of answers to the sample cases. Other answers may be possible. In Sample Case #$1$, Grace will follow the route $A_{1,1}$, $A_{2,1}$, $A_{2,2}$, $A_{1,2}$, and finally $A_{1,1}$. Note that `ESWN` is the only other possible valid answer. The image below shows one of the possible routes for Sample Case #$1$. :::align{center}  ::: The image below shows one of the possible routes for Sample Case #2. :::align{center}  ::: ### Limits $1 \le T \le 100$. $1 \le R \le 200$. $1 \le C \le 200$. All characters in the grid are from the set $\{\#, \ast\}$. The first character of the first line of the input grid for each test case is a `*` character, i.e. $B_{1,1} = \ast$. **Test Set $1$** A block contains buildings if and only if the row number and column number of it are divisible by $2$. i.e. $B_{i,j} = \# \iff ((i \bmod 2 = 0) \land (j \bmod 2 = 0))$. **Test Set $2$** No extra constraints.