시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2024 | 935 | 718 | 47.206% |
상근이는 건강을 위해 산책을 하려고 한다.
상근이가 사는 마을은 아래 그림과 같이 가로 방향 도로가 (H+1)개, 세로 방향 도로가 (W+1)개가 바둑판 모양으로 배치되어 있다. 상근이네 집은 가장 왼쪽 위 교차로에 있으며, 이곳에서 산책을 시작한다.
(a,b)는 위쪽에서 a번째, 왼쪽에서 b번째에 있는 교차로이다. 예를 들어, 상근이네 집은 교차로 (1,1)에 있다.
상근이는 산책 경로가 매일 달라야 질리지 않고 산책을 할 수 있다고 생각한다. 따라서, (1,1)에서 (H,W)까지 H × W개 교차로에 오른쪽을 뜻하는 오 또는 아래를 뜻하는 아를 쓰고, 다음과 같은 규칙에 따라서 산책을 하기로 했다.
교차로에 쓰여 있는 문자가 오라면, 이 문자를 지우고 아를 쓴다. 그 다음에 오른쪽으로 진행한다. 만약, 교차로에 쓰여 있는 문자가 아라면, 이 문자를 지우고 오를 쓴뒤, 아래로 진행한다.
이렇게 산책을 하다가 가장 오른쪽이나 아래쪽 도로에 도착하면 산책을 종료한다.
상근이는 이런 방법으로 산책을 계속 한다면, N번째 산책 경로가 어떻게 될지 궁금해졌다. H, W와 각 교차로에 써놓은 글자가 주어졌을 때, N번째 산책 경로를 구하는 프로그램을 작성하시오.
첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107)
둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은 오른쪽을 의미하는 '오'이다.
N번째 산책에서 산책을 종료하는 교차로가 (i,j)라고 할 때, i와 j를 공백으로 구분하여 출력한다.
3 4 3 1 0 1 1 0 1 0 0 1 0 1 0
1 5