| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 1049 | 184 | 135 | 19.622% |
개구리는 $N \times M$ 격자 모양의 청정한 서식지에 살고 있다. 가장 왼쪽 위 칸의 좌표는 $(1,1)$이고 가장 오른쪽 아래 칸의 좌표는 $(N,M)$이다. 각 격자 칸에는 개구리밥이 있는데, 개구리는 자신이 위치한 칸에 있는 개구리밥을 먹고 힘을 내서 격자 칸 사이를 점프할 수 있다. 격자 칸 $(i,j)$에 있는 개구리밥을 먹으면 해당 칸에서 상하좌우 중 한 방향으로 정확히 $a_{i,j}$칸 점프한다. 단, 서식지 밖으로는 점프할 수 없다.
왠지 오늘 기분이 시니컬해진 개구리는 어서 집에 가서 쉬고 싶다. 그래서 오늘만큼은 최대 한 번 개구리밥을 무시하고 점프하기로 했다. 개구리밥을 무시하고 점프할 때는 상하좌우 중 한 방향으로 서식지 내에서 원하는 칸만큼 점프할 수 있다.
청정한 서식지의 정보와 개구리의 위치와 개구리 집의 위치가 주어졌을 때, 개구리가 집에 가기 위한 최소 점프 횟수를 구해주자.
첫 번째 줄에 $N,ドル $M$이 주어진다. (1ドル \le N, M \le 1,000円$)
두 번째 줄에 $r_f,ドル $c_f,ドル $r_h,ドル $c_h$가 주어진다. 개구리의 위치는 $(r_f,c_f)$이고 개구리 집의 위치는 $(r_h,c_h)$라는 뜻이다. (1ドル \le r_f, r_h \le N,ドル 1ドル \le c_f, c_h \le M$)
세 번째 줄부터 $N$개의 줄에 걸쳐 $a_{i,j}$가 주어진다. (1ドル \le a_{i,j}\le 1,000円$)
개구리가 집에 가기 위한 최소 점프 횟수를 출력한다. 단, 개구리가 집에 갈 수 없다면 -1을 출력한다.
4 5 2 1 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3
$(2,1) \rightarrow (2,5) \rightarrow (3,5) \rightarrow (4,5)$순으로 점프 세 번 만에 갈 수 있다.
1 7 1 1 1 7 6 3 1 1 2 4 1
1
$(1,1) \rightarrow (1,7)$순으로 점프 한 번에 갈 수 있다.
3 3 2 2 2 2 1 3 1 3 4 3 1 3 1
0
개구리는 집에 있으므로 점프하지 않아도 된다.
4 4 4 4 1 1 1 4 9 4 4 3 7 5 1 4 6 9 8 3 4 1
-1
개구리는 어떤 방법으로도 집에 갈 수 없다.