시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 69 6 5 9.434%

문제

새로 생긴 놀이 동산에 놀러간 해인이는 잠시 한눈을 판 사이에 친구들을 놓쳤다. 준비성이 철저한 해인이는 미리 자신이 길을 잃을 것을 대비해서 약속 장소를 친구들에게 알려주었기 때문에 그 장소로 가능한 한 빨리 가려고 한다. 놀이동산은  N*M의 격자로 이루어져 있고 각각의 격자를 모두 독특한 행사를 하고 있기 때문에 지나가는데 드는 비용이 다르다. 맨 왼쪽 위의 격자는 (1,1)이고 가장 오른쪽 아래 격자는 (N,M)이다. 그리고 각 격자를 지나가는데 걸리는 비용을 나타난 행렬을 C라고 하면 Cij는 (i,j)번 격자를 지나가려면 1/Cij의 비용이 든다는 것을 의미한다. 

해인이는 격자위의 특정 지점에 있을때 그 지점의 위, 아래, 왼쪽, 오른쪽으로 순식간에 이동할 수 있다.(즉, 시간이 들지 않는다) 

그리고 시간은 0분~1분, 1분~2분, 2분~3분, … 같은 구간으로 나누어 볼 수 있으며 이때 격자를 이동하는데에 한가지 조건이 생긴다. 각 시간 구간에서 거쳤던 격자의 총 비용이 1이하여야 한다.

해인이가 현재 있는 위치 (Sx, Sy)와 약속장소 (Dx, Dy)가 주어지고 행렬 C가 주어진다고 할때 해인이의 현재 위치에서 약속 장소까지 가는데 걸리는 최소의 시간을 구하라.

다음의 예제를 생각해보자. N=1, M=5이고 C = {22334}, Sx = 1, Sy = 1, Dx = 1, Dy = 5라면 놀이동산은 다음과 같은 그림이라고 할 수 있다.

이때 첫번째 시간 구간 (0분~1분) 에서 위치를 (1,2)까지 갈 수 있다. 왜냐하면 이 구간에 있었던 격자의 총 비용이 ½ + ½ <= 1이기 때문이다. 하지만, (1,3)까지는 ½ + ½ + ⅓ > 1이기 때문에 가지 못한다.

(1분~2분)에서는 (1,3)까지 갈 수 있다. 하지만, (1,4)까지는 갈 수 없다. ½ + ⅓ + ⅓ > 1.

(2분~3분)에서는 (1,5)까지 갈 수 있다. ⅓ + ⅓ + ¼ <= 1

결국 필요한 최소의 시간은 3분이다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 놀이동산의 크기 정수 N, M이 주어진다. ( 1<= N , M <= 50 인 ). 두 번째 줄에는 N개의 줄에 걸쳐서 행렬 C가 주어진다. N+2 번째 줄에는 정수 Sx, Sy, Dx, Dy가 주어진다. ( 1 <= Sx, Dx <= N,  1 <=Sy, Dy <= M ).

출력

각각의 Test case에 대해서 해인이의 현재 위치에서 목표 위치까지 가는데 필요한 최소 시간을 출력하라. 목표 위치까지 갈 수 없는 경우에는 -1을 출력한다.

예제 입력

2
1 5
22334
1 1 1 5
3 2
55
52
55
1 2 3 2

예제 출력

3
1

힌트

출처

  • 문제의 오타를 찾은 사람: myungwoo