시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
25 초 (추가 시간 없음) | 1024 MB | 17 | 11 | 10 | 76.923% |
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≤i≤2R$ and $1≤j≤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×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≤i≤R$ and $1≤j≤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 two 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 four cells: $A_{2i-1,2j-1}$, $A_{2i-1,2j}$, $A_{2i,2j-1}$, and $A_{2i,2j}$. If $B_{i,j}=$ #
, all four of the cells in $B_{i,j}$ are occupied by a building. Otherwise, if $B_{i,j}=$ *
, all four 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.
#
,*
}.*
character, i.e. $B_{1,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}=$ #
$⟺((i \text{ mod } 2=0)$ and $(j \text{ mod }2=0))$.
No extra constraints.
3 1 1 * 2 2 ** *# 3 4 **** *#*# ****
Case #1: SENW Case #2: SSSENNEENWWW Case #3: ESSSSEEENNNWWNEEEEESWWSSSEESWWWWWWWNNNNN
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.
The image below shows one of the possible routes for Sample Case #2.
3 3 1 * * # 1 3 *#* 3 4 **#* **#* ****
Case #1: SSSENNNW Case #2: IMPOSSIBLE Case #3: ESSSSENNNNESSSSEEENNNNESSSSSWWWWWWWNNNNN
The image below shows one of the possible routes for Sample Case #1.
In Sample Case #2, it is impossible for Grace to travel to any cell in $B_{1,3}$ from $A_{1,1}$.
Contest > Google > Kick Start > Google Kick Start 2022 > Round B D번