닐가이

닐가이는 인도산 영양으로 풀이 쉽게 자랄 수 없는 가파른 절벽에 살고 있다. 닐가이는 절벽 타기에 매우 능하며 아주 가파른 절벽에서도 몸의 균형을 잘 잡는다. 그렇지만 키가 작기 때문에 1 피트 이상 높이 차가 있는 바위 사이에는 점프하여 이동할 수 없다. 닐가이 한 마리가  사각 그리드의 맨 왼쪽 위 귀퉁이 칸에 있다. 그리드의 한 칸에 바위가 하나씩 있다. 반대쪽 귀퉁이, 즉 맨 오른쪽 아래 칸에 풀숲이 있다.

닐가이는 현재 위치에서 풀숲까지 가는 길을 찾으려고 하고 있다. 닐가이는 바위를 뛰어 넘을 수는 없고, 인접한 네 칸으로 이동할 수 있다. 그러나 닐가이는 그리드를 벗어 날 수 없다. 더더구나 닐가이는 1 피트만 점프하여 뛰어 오르거나 내릴 수 있으므로, 높이 차가 1 이하인 칸으로만 이동할 수 있다. 당신이 할 일은 닐가이를 도와서 풀숲으로 가는 길을 찾는 것이다. 길이 여럿 존재하면 그 중 하나만 찾으면 되고, 길이 없을 수도 있다.

예를 들어 아래 그림 (a)와 같은 그리드를 고려해 보자. 그리드 칸에 쓰인 숫자는 바위의 높이를 나타내고 단위는 피트이다. 그림 (b)는 닐가이가 풀숲으로 갈 수 있는 길을 나타낸다. 경로는 a, b, c, ... 순서로 라벨이 붙은 칸을 지나면 된다.

7	9	8	5
6	3	2	4
5	4	1	5
2	6	1	1

그림 (a)

7 (a)	9	8	5
6 (b)	3 (e)	2 (f)	4
5 (c)	4 (d)	1 (g)	5
2	6	1 (h)	1 (i)

그림 (b)

프로그램 이름은 path.cpp, 실행 파일의 이름은 path.exe, 프로그램 설명 파일 이름은 path.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에 각각 그리드의 행과 열을 수를 나타내는 과 이 주어진다. 이때, 이다. 다음 개의 줄 각각에는 음이 아닌 정수가 개 주어지는데, 번째 줄의 번째 정수는 번째 행 번째 열에 있는 바위의 높이를 내고, 높이는 10 이하이다.

2004 가을학기 문제해결기법	문제 #5

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 닐가이가 풀숲으로 가는 길이 없으면 첫째 줄 한 줄에 정수 0을 출력한다. 만약 길이 있으면 첫째 줄에 정수 1을 출력한 다음 길을 출력한다. 경로는 그것이 지나는 칸의 수만큼의 줄에 출력하는데,  맨 처음 닐가이가 위치한 칸의 행과 열 번호를 나타내는 1 1에서 시작하여 그것이 지나는 칸의 행과 열의 번호를 순서대로 출력하고, 마지막은 풀숲이 있는  을 출력한다. 행 번호와 열 번호 사이에는 공백을 하나 둔다.

입력과 출력의 예

입력(input.txt)

4 4

7 9 8 5

6 3 2 4

5 4 1 5

2 6 1 1

출력(output.txt)

1

1 1

2 1

3 1

3 2

2 2

2 3

3 3

4 3

4 4