시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB52101035.714%

문제

가희는 언니 방에 있는 가방과 베개 위에서 똬리를 틀고 자는 것을 좋아합니다.

[그림 1] 언니 가방 위에 올라와서 똬리를 틀고 있는 가희

가희는 언니 방에 언니가 있는 줄 알고 들어갔지만, 평소와 다르게 엄마 주인이 침대 위에 있었습니다. 엄마 주인은 언니 방에 들어온 가희를 내쫓고 언니의 가방과 베개 위에서 자지 못하도록 장애물과 고도 1의 나무토막 여러 개를 언니 방에 설치하였습니다.

엄마 주인이 언니 방을 나가고 나서야, 가희는 다시 언니 방에 들어올 수 있게 되었습니다. 그런데, 엄마 주인이 설치해 놓은 장애물과 나무토막들 때문에 가희가 좋아하는 베개와 가방으로 갈 수 없었습니다. 이곳저곳을 돌아다니다가 지친 가희는 언니 방의 좌표 (x, y)에서 오빠 주인에게 도움을 요청하였습니다. 마침 오빠 주인은 ?로 표시된 곳에 가로 1칸, 세로 1칸을 차지하는 경사로를 설치할 수 있는 장치를 가지고 있었습니다. 가희는 이 장치를 오빠 주인에게 받아, 장치를 이용해서 경사로를 설치할 수 있는 모든 곳에 경사로를 설치한 후 베개나 가방이 있는 곳으로 이동하려고 합니다.

경사로가 설치된 방향이란 고도가 낮은 쪽에서 높은 쪽으로 올라가는 방향을 의미합니다. 이 방향은 북쪽을 나타내는 N, 서쪽을 나타내는 W, 동쪽을 나타내는 E, 남쪽을 나타내는 S 이렇게 4가지가 있습니다. 경사로가 설치된 방향에 따라 이동할 수 없는 방향도 있습니다. 아래 그림에서 경사로가 설치되지 않은 곳은 고도가 0 또는 1인 곳입니다.

[그림 2-1(왼), 그림 2-2(오)] 경사로가 설치된 방향과 이동할 수 없는 방향

[그림 2-1] 처럼 W 방향이나 E 방향으로 설치된 경사로에서 위쪽, 아래쪽으로 갈 수 없고, 위쪽이나 아래쪽에서 W 방향이나 E 방향으로 설치된 경사로로 올 수 없습니다. [그림 2-2] 처럼 N 방향이나 S 방향으로 설치된 경사로에서 왼쪽, 오른쪽으로 갈 수 없고, 왼쪽이나 오른쪽에서 N 방향이나 S 방향으로 설치된 경사로로 올 수 없습니다.

 

[그림 3] 위에서 바라본 경사로의 방향

[그림 3]은 경사로의 방향에 따라 고도가 0인 곳에서 1인 곳으로 어떻게 연결하는지 보여줍니다. 아래 [그림 4]를 보겠습니다.

[그림 4] W 방향으로 설치된 경사로를 측면에서 본 모습

좌표 (1, 2)에 W 방향으로 경사로가 설치되었다고 해 보겠습니다. 이 경우, W 방향으로 설치된 경사로는 고도가 1인 (1, 1)과, 고도가 0인 (1, 3)을 이어주게 됩니다.

[그림 5] E 방향으로 설치된 모습을 측면에서 본 모습

반면에, 좌표 (1, 1)의 고도가 1이고, (1, 3)의 고도가 0이고, (1, 2)에 E 방향으로 경사로가 설치된 경우, 가희는 (1, 1)에서 (1, 2)로, 혹은 (1, 2)에서 (1, 3)으로 갈 수 없습니다.

가희는 다음 규칙을 만족하면서 이동해야 합니다. 안 그러면 무서운 엄마 주인이 가희가 언니 방에 들어왔다는 사실을 눈치챌 것입니다.

  • 현재 가희가 있는 곳으로부터 상하좌우로 인접한 곳으로만 이동할 수 있습니다.
  • 벽이 있는 곳으로 이동할 수 없습니다.
  • 고도가 다른 곳으로 이동할 때, 경사로를 통해서만 이동할 수 있습니다.
  • 가희는 맵 바깥으로 나갈 수 없습니다.

가희는 오빠 주인이 가지고 온 장치를 이용해서 경사로를 설치할 수 있는 모든 곳에 경사로를 적절한 방향으로 설치하려고 합니다. 그렇게 해서, 오빠에게 도움을 요청한 곳으로부터 베개나 가방이 있는 곳으로 갈 수 있게 하려고 합니다. 가희가 목적을 달성할 수 있게 도와주세요.

입력

첫 번째 줄에 언니 방의 세로 길이 R과 가로 길이 C가 공백으로 구분되어 주어집니다. RC는 1 이상 738 이하의 정수입니다.

두 번째 줄부터 R개의 줄에 걸쳐 길이가 C인 문자열이 주어집니다. i번째 문자열의 j번째 문자는 아래 6개 중 하나로 좌표 (i, j)의 언니 방의 정보를 의미합니다.

  • ? : 경사로를 설치할 수 있는 곳
  • . : 고도가 0인 곳
  • 1 : 고도가 1인 곳 (언니 방에 설치된 나무토막의 위를 의미)
  • # : 가희가 절대로 갈 수 없는
  • P : 베개
  • B : 가방

그다음 줄에 가희가 오빠에게 도움을 요청한 곳의 x좌표와 y좌표가 공백으로 구분되어 주어집니다. x는 1 이상 R 이하의 정수이며, y는 1 이상 C 이하의 정수입니다.

출력

  • 가희가 목적을 달성할 수 있도록 '?'가 표시된 모든 곳에 경사로를 설치할 수 있다면 아무것이나 출력해도 정답으로 인정됩니다.
    • '?'가 표시된 모든 곳에는 'N', 'W', 'E', 'S' 중 하나가 있어야 합니다.
    • 그 외에 지역은 변형을 가하지 않아야 합니다. 예를 들어, 벽이 있던 곳에 벽을 없애서 고도를 1로 만드는 것은 허용되지 않습니다.
  • 가희가 '?'으로 표시된 모든 곳에 어떤 방법으로 경사로를 설치해도 목적을 달성할 수 없다면 -1을 출력해 주세요.

제한

  • 경사로를 설치할 수 있는 곳의 고도는 0입니다.
  • 베개와 가방이 있는 곳의 고도는 0입니다.
  • 가희가 현재 있는 곳인, 좌표 (x, y)에는 '#'이나 '?'가 없습니다.
  • 0 ≤ '?' (설치할 수 있는 경사로)의 개수 ≤ 18
  • 경사로를 설치할 수 있는 곳들은 서로 인접하지 않습니다.

예제 입력 1

1 5
.?1?P
1 1

예제 출력 1

.E1WP

1행 2열과 1행 4열에 경사로를 설치할 수 있습니다. 1행 2열에는 E 방향으로, 1행 4열에는 W 방향으로 경사로를 설치해 봅시다.

[그림 6] 문제의 답과 관찰자의 시점

[그림 7] 관찰자의 시점에서 본 답

그러면 1행 1열에 있는 가희는 E 방향으로 설치된 경사로를 통해 1행 3열로 갈 수 있고, W 방향으로 설치된 경사로를 통해 1행 5열로 갈 수 있습니다.

예제 입력 2

3 5
.....
..?.#
111?B
1 1

예제 출력 2

.....
..S.#
111WB

예제 입력 3

3 5
.....
....?
...#B
1 1

예제 출력 3

-1

예제 입력 4

6 1
.
?
1
?
B
B
1 1

예제 출력 4

.
S
1
N
B
B