P16876 [GKS 2022 #B] Hamiltonian Tour

Hamilton 是加拿大多伦多附近的一座城市，也是一个适合徒步旅行的好地方。 在本问题中，Hamilton 被表示为一个由 $2R$ 行 $2C$ 列单位单元格组成的网格，每个单元格要么是空的（用 `*` 表示），要么包含一座建筑（用 `#` 表示）。第 $i$ 行第 $j$ 列的单元格记为 $A_{i,j}$，其中 $1 \le i \le 2R$，$1 \le j \le 2C$。不能进入包含建筑的单元格，且只能移动到与当前单元格共享一条边的相邻单元格（不仅仅是角点）。网格满足：如果将网格均匀划分为 $2 \times 2$ 的单元格块，则每个块中的四个单元格要么全部为空，要么全部被建筑占据。将由单元格 $A_{2i-1,2j-1}$、$A_{2i-1,2j}$、$A_{2i,2j-1}$ 和 $A_{2i,2j}$ 组成的块记为 $B_{i,j}$，其中 $1 \le i \le R$，$1 \le j \le C$。 Grace 是一位游客，她想参观 Hamilton 中的所有空单元格。Grace 当前位于单元格 $A_{1,1}$ 中。重复访问同一个单元格可能会让她感到无聊。因此，Grace 希望恰好访问每个空单元格一次，并最终回到单元格 $A_{1,1}$。你能帮助 Grace 提供一个字符串（由方向移动字符 $\{N, E, S, W\}$ 组成，分别表示向北、向东、向南、向西移动一个单位），使得 Grace 按照该字符串移动，能够访问每个空单元格一次，并最终回到 $A_{1,1}$。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $R$ 和 $C$。 接下来的 $R$ 行，每行包含 $C$ 个字符。 其中第 $i$ 行第 $j$ 个字符表示块 $B_{i,j}$，该块由以下四个单元格组成：$A_{2i-1,2j-1}$、$A_{2i-1,2j}$、$A_{2i,2j-1}$ 和 $A_{2i,2j}$。 如果 $B_{i,j} = \#$，则 $B_{i,j}$ 中的四个单元格全部被建筑占据。 否则，如果 $B_{i,j} = \ast$，则 $B_{i,j}$ 中的四个单元格全部为空。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是问题的答案，具体如下： 如果无解，则 $y$ 应为 `IMPOSSIBLE`。否则，$y$ 应为一个由集合 $\{N, E, S, W\}$ 中字符组成的序列，表示一条有效路径中的单位移动（分别对应北、东、南、西），从 $A_{1,1}$ 出发，如上文所述。 注意，你的最后一步移动应使你回到 $A_{1,1}$；这一步不算作重复访问同一单元格。 如果存在多个有效解，你可以输出其中任意一个。

样例输出展示了一组答案。其他答案也可能存在。 在样例 #1 中，Grace 将按照路径 $A_{1,1}$、$A_{2,1}$、$A_{2,2}$、$A_{1,2}$ 移动，最后回到 $A_{1,1}$。注意 `ESWN` 是另一个可能的有效答案。 下图展示了样例 #1 的一种可能路径。 :::align{center}  ::: 下图展示了样例 #2 的一种可能路径。 :::align{center}  ::: ### 限制条件 $1 \le T \le 100$。 $1 \le R \le 200$。 $1 \le C \le 200$。 网格中的所有字符均来自集合 $\{\#, \ast\}$。 每个测试用例输入网格的第一行的第一个字符为 `*`，即 $B_{1,1} = \ast$。 **测试集 1** 块中包含建筑当且仅当其行号和列号均为偶数。即 $B_{i,j} = \# \iff ((i \bmod 2 = 0) \land (j \bmod 2 = 0))$。 **测试集 2** 无额外限制。 翻译由 DeepSeek V4 Pro 完成