만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

오늘부터 우리는 (Me gustas tu)

면접 대비

시간 제한1초메모리 제한1024 MB

요약
N×M 격자와 목표 칸 (a,b)가 주어졌을 때, 어느 칸에서 출발하든 바람을 따라 (a,b)에 도달하도록 각 칸의 바람 방향을 정합니다.
난이도

보통10점 중 4점

유형
BFS, 그래프, 구현
정답자
아직 제출이 없습니다

문제

널 향한 설레임을 오늘부터 우리는

꿈꾸며 기도하는 오늘부터 우리는

저 바람에 노을 빛 내 맘을 실어 보낼게

그리운 마음이 모여서 내리는

바람이 부는 들판에서, 나의 마음을 너에게 실어 보내려고 한다.

들판은 N×MN \times M 크기의 격자로 나타낼 수 있다. 각 칸은 (x,y)(x,y) (0≤x<N0 \leq x < N, 0≤y<M0 \leq y < M)와 같은 좌표로 나타낸다. 이 좌표는 위에서 x+1x+1번째, 왼쪽에서 y+1y+1번째에 있는 칸을 뜻한다. 들판의 각 칸에는 동, 서, 남, 북 중 한 방향으로 바람이 분다. 들판에는 네가 (a,b)(a,b) 칸에 서 있고, 나의 마음이 격자 어딘가에 정확히 1개 있다.

나의 마음이 칸 (i,j)(i,j)에 있으면 다음과 같이 이동한다.

  • 칸 (i,j)(i,j)에 동쪽 바람이 불면 (i,j+1)(i,j+1)로 이동한다.
  • 칸 (i,j)(i,j)에 서쪽 바람이 불면 (i,j−1)(i,j-1)로 이동한다.
  • 칸 (i,j)(i,j)에 남쪽 바람이 불면 (i+1,j)(i+1,j)로 이동한다.
  • 칸 (i,j)(i,j)에 북쪽 바람이 불면 (i−1,j)(i-1,j)로 이동한다.

나의 마음이 네가 있는 칸에 닿으면 마음이 전해지고, 격자의 경계를 벗어나면 사라진다. 둘 중 어느 쪽도 아니면 마음은 계속 이동한다.

나의 마음이 네가 있는 칸에서 시작할 수도 있다. 이 경우 마음이 바로 전해진다.

나의 마음이 어디에서 출발하든 항상 너에게 전해질 수 있다고 한다. 이러한 바람의 배치를 구해 보자.

입력

첫째 줄에 NN과 MM이 주어진다.

둘째 줄에 aa와 bb가 주어진다. (0≤a<N0 \leq a < N, 0≤b<M0 \leq b < M)

출력

NN개 줄에 걸쳐 바람의 배치를 나타내는 MM개의 문자를 출력한다.

칸 (i,j)(i,j)에 바람이 동쪽으로 불면 i+1i+1번째 줄의 j+1j+1번째 글자로 E를 출력한다. 서쪽, 남쪽, 북쪽으로 불면 같은 방식으로 W, S, N을 출력한다.

가능한 바람의 배치가 여러 개이면 아무거나 출력해도 된다.

모든 입력에 대해 가능한 바람의 배치가 있음을 증명할 수 있다.

제한

  • 1≤N,M≤501 \leq N, M \leq 50

예제1

  1. 예제 1

    입력
    3 3
    1 1
    
    예상 출력
    SSS
    EEW
    NNN