BOJ 17391 무한부스터

문제 링크:

문제 내용

$N$행 $M$열의 사각 격자의 각 칸에 양의 정수 $a_{ij}$가 쓰여 있습니다.

당신은 1행 1열에서 시작하여 최소한의 이동으로 $N$행 $M$열에 도달해야 합니다.

당신은 다음과 같은 행동을 할 수 있습니다.

• 현재 있는 칸이 $i$행 $j$열이고, 그 칸에 쓰여 있는 수가 $a_{ij}$이면, 1 이상 $a_{ij}$ 이하의 정수 거리만큼 오른쪽으로 이동하거나, 1 이상 $a_{ij}$ 이하의 정수 거리만큼 아래로 이동할 수 있습니다. 이때 격자 밖으로는 이동할 수 없습니다.

이때 최소 이동 횟수를 구하세요.

입력

첫 번째 줄에는 $N$과 $M$이 주어집니다. ($1 \le N, M \le 300$, $N \times M \ge 2$)

다음 줄부터 $N$줄에 걸쳐서, 각 줄에 $M$개의 정수 $a_{ij}$가 주어집니다. ($1 \le a_{ij} \le \min(N, M)$)

출력

최소 이동 횟수를 출력합니다.

문제 풀이