시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 546 67 43 13.738%

문제

평소 탱자탱자 놀던 건우가 마지막 날에 과제를 시작했다. 건우는 피곤이 몰려왔는지, 그만 잠이 들고 말았다! 그러고는 꿈을 꿨다. 그곳은 미로였는데 너무 현실성이 없었던 탓에 건우는 꿈이란 걸 알아챘다. 얼른 꿈에서 깨려고 노력했지만 깰 수 없었다. 왜냐하면 건우가 꿈에서 깨어나려면 반드시 미로를 탈출해야만 했기 때문이다. 미로의 특징은 다음과 같다.

  • n×n미로이며 가장 왼쪽 위가 출발지, 가장 오른쪽 아래가 도착지이다. 출발지와 도착지에는 벽이 없음이 보장된다.
  • 건우는 상하좌우로만 움직일 수 있으며, 벽을 넘는 것을 제외하면 한 번 이동할 때 벽이 없는 인접한 칸으로 이동한다.
  • 초기 상태는 첫 번째 날 낮으로 시작하고, 건우가 m번 이동할 때 마다 낮에서 밤 또는 밤에서 낮으로 바뀐다.
  • 밤에는 낮과 달리 추가로 벽을 넘을 수 있다. 벽을 넘을 때는 가려는 방향의 인접한 칸에 벽이 있어야 하며, 건우가 서 있을 수 있는 칸이 나올때까지 연속된 벽을 넘는다.
  • 벽을 넘는 도중에 방향을 바꿀 순 없으며, 벽을 넘으면 1번 이동한 것으로 간주한다.

다음은 벽을 넘는 것에 대한 예시다. 주황색은 건우가 있는 곳 파란색은 벽이다.

위 경우는 벽을 넘을 수 있다.

위 경우처럼 벽을 넘었을 때 미로를 벗어날 경우에는 이동할 수 없다.

건우가 가장 빨리 탈출할 수 있는 날이 몇 번째 날의 낮 혹은 밤인지를 구해서 건우가 잠에서 깨도록 만들자!

입력

첫 번째 줄에 n, m이 주어진다. (1 ≤ ≤ 500, 1 ≤ ≤ 10)

두 번째 줄부터 n개의 각 줄에 0 또는 1이 공백을 사이에 두고 n개씩 주어진다.
이 때 0 은 벽이 없어 건우가 설 수 있는 곳, 1 은 벽이 있어 건우가 설 수 없는 곳을 의미한다.

출력

건우가 가장 빨리 탈출할 수 있는 날이 몇번째 날인지, 그리고 낮이면 "sun", 밤이면 "moon"을 공백으로 구분하여 함께 출력한다.
예를 들어, 2번째 날 밤일 경우, "2 moon" 을 출력하고, 3번째 날 낮일 경우, "3 sun" 을 출력한다. 만약 탈출할 수 없을 경우 -1을 출력한다.

예제 입력 1

5 2
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0

예제 출력 1

2 sun

가장 빨리 탈출하는 경로는 (0,0)→(0,1)→(0,2)→(4,2)→(4,3)→(4,4) 이며

시간의 흐름은 (1 sun)→(1 sun)→(1 moon)→(1 moon)→(2 sun)→(2 sun) 이다.

예제 입력 2

3 1
0 1 0
1 0 0
0 0 0

예제 출력 2

-1

(0,0)에서 가만히 있으면 시간이 흐르지 않으므로 탈출할 수 없다.