아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

격자 점프

면접 대비

시간 제한2초메모리 제한256 MB

요약
숫자 격자의 왼쪽 위 칸에서 시작해 적힌 숫자만큼 상하좌우로 점프하여 오른쪽 아래 칸에 도달하는 최소 이동 횟수를 구합니다.
난이도

보통10점 중 4점

유형
BFS, 그래프
정답자
아직 제출이 없습니다

문제

n×mn \times m 격자의 각 칸에는 숫자가 하나씩 적혀 있다. 숫자가 kk인 칸에서는 상하좌우 네 방향 중 하나를 골라 정확히 kk칸을 건너뛸 수 있고, 이것을 이동 한 번으로 센다. 격자 밖으로 나가는 이동은 할 수 없으며, 한쪽 끝에서 반대쪽 끝으로 이어지지도 않는다.

왼쪽 위 칸에서 출발해 오른쪽 아래 칸에 도착하는 데 필요한 최소 이동 횟수를 구하라.

입력

첫째 줄에 격자의 크기를 나타내는 두 정수 nn과 mm이 공백으로 구분되어 주어진다 (1≤n,m≤5001 \le n, m \le 500). nn과 mm 중 적어도 하나는 1보다 크다.

다음 nn개 줄에는 각 줄마다 숫자 mm개가 공백 없이 주어진다. 각 숫자는 0 이상 9 이하이다.

첫 줄의 첫 문자가 왼쪽 위 칸이고, 마지막 줄의 마지막 문자가 오른쪽 아래 칸이다.

출력

왼쪽 위 칸에서 오른쪽 아래 칸까지 가는 데 필요한 최소 이동 횟수를 한 줄에 출력한다. 도착할 수 없으면 IMPOSSIBLE을 출력한다.

예제3

  1. 예제 1

    입력
    2 2
    11
    11
    
    예상 출력
    2
    
  2. 예제 2

    입력
    2 2
    22
    22
    
    예상 출력
    IMPOSSIBLE
    
  3. 예제 3

    입력
    5 4
    2120
    1203
    3113
    1120
    1110
    
    예상 출력
    6