問題
방금 세계에서 가장 쉬운 미로에 들어왔다. 당신은 한 변의 길이가 N인 N × N 단위 격자의 북서쪽 칸에서 시작하며, 남동쪽 칸에 도달해야 한다. 가능한 이동은 두 가지뿐이다: 동쪽으로 한 칸 이동, 남쪽으로 한 칸 이동. 어떤 칸으로든 이동할 수 있지만, 격자를 벗어나게 되는 이동은 할 수 없다.
당신은 세계 최초로 이 미로를 푸는 사람이 될 생각에 신이 나 있었지만, 발자국을 발견했다. 당신의 라이벌인 미로의 리디아(Labyrinth Lydia)가 이미 위와 같은 규칙으로 미로를 풀어 버렸다!
당신은 독창적인 사상가이므로 리디아의 움직임을 하나도 재사용하고 싶지 않다. 구체적으로, 리디아의 경로에 어떤 칸 A에서 인접한 칸 B로 가는 단위 이동이 포함되어 있다면, 당신의 경로에는 A에서 B로 가는 이동이 포함될 수 없다. (하지만 그 경우에도, A를 방문하거나 B를 방문하는 것은 괜찮다. A에서 B로만 가지 않으면 된다.) 이러한 경로를 찾아라.
아래 그림에서 리디아의 경로는 파란색으로 표시되어 있고, 당신이 사용할 수 있는 한 가지 가능한 경로는 주황색으로 표시되어 있다:
輸入
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다.
T개의 테스트 케이스가 이어지며,
각 테스트 케이스는 두 줄로 이루어진다.
첫 줄에는 위에서 설명한 미로의 크기 N이 주어진다.
둘째 줄에는 길이 2N - 2의 문자열 P가 주어지는데,
각 문자는 동쪽을 의미하는 대문자 E 또는 남쪽을 의미하는 대문자 S이며,
이는 리디아의 유효한 경로를 나타낸다.
輸出
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라.
여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고,
y는 길이 2N - 2의 문자열로,
각 문자가 동쪽을 의미하는 E 또는 남쪽을 의미하는 S이며,
위에서 설명한 대로 리디아의 경로와 충돌하지 않는 당신의 유효한 경로를 나타낸다.
적어도 하나의 답이 존재함이 보장된다.
範例
2
2
SE
5
EESSSESE
Case #1: ES
Case #2: SEEESSES
需要登入才能撰寫程式碼。