어린이 놀이동산에 돌-블록이 타일처럼 배치되어 있는 마당이 있다. 이 마당은 아래 그림처럼 n×m 크기의 격자로 표시된다. 격자의 칸에 있는 값은 돌-블록의 높이이다.

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

이 마당의 입구는 (1,1) 위치이고, 출구는 (n,m) 위치이다. 이 마당에서 즐길 수 있는 놀이 중에는 입구에서 출구까지 길을 찾는 게임이 있다. 게임 참가자는 각 블록에서 동서남북으로 인접한 블록으로 점프하여 건너갈 수 있는데, 높이 차이가 1보다 큰 경우에는 건너갈 수 없다. 또한 출구를 제외하고는 마당 밖으로 나갈 수 없다. 위 예에서 출구인 (4,4) 블록까지 이동하기 위해서는 (1,1), (2,1), (3,1), (3,2), (2,2), (2,3), (3,3), (4,3), (4,4) 블록을 순서대로 지나가면 된다. 이 놀이는 입구에서 시작하여 출구로 나갈 때까지 밟고 지나간 블록의 개수가 작을수록 높은 점수를 얻게 된다.

게임 참가자가 마당의 입구에서 시작하여 가장 작은 개수의 블록을 밟으면서 출구로 도착할 수 있는 길을 찾는 프로그램을 작성하시오.

1. 첫째 줄에 마당의 크기 n×m을 나타내는 두 개의 정수 n과 m이 차례대로 주어진다. (2≤n≤1,000, 2≤m≤1,000)
2. 그 다음 n개의 줄에는 m개의 정수가 주어지는데, i+1번째 줄의 j-번째 정수는 i-번째 행 j-번째 열에 있는 블록의 높이를 나타낸다. 돌 블록의 높이는 1 이상 9이하이다.

1. 게임 참가자가 출구까지 갈 수 없으면 첫 줄에 0을 출력한다.
2. 만약 출구가 가는 길이 있으면, 가장 작은 개수의 블록으로 구성된 길을 찾아서 그 길을 구성하는 블록의 개수를 첫 줄에 출력한다.

교원프로그래밍 2011