2781번

수정 전

시간 제한 메모리 제한
1 초 128 MB

문제

  새로 생긴 놀이 동산에 놀러간 해인이는 한눈을 판 사이에 친구들을 놓쳤다. 준비성이 철저한 해인이는 미리 자신이 길을 잃을 것을 대비해서 약속 장소를 친구들에게 알려주었기 때문에 그 장소로 가능한 한 빨리 가려고 한다. 놀이동산은  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,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에 대해서 해인이의 현재 위치에서 목표 위치까지 가는데 필요한 최소 시간을 출력하라.

예제 입력

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

예제 출력

3 1

힌트

수정 후

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

문제

  새로 생긴 놀이 동산에 놀러간 해인이는 한눈을 판 사이에 친구들을 놓쳤다. 준비성이 철저한 해인이는 미리 자신이 길을 잃을 것을 대비해서 약속 장소를 친구들에게 알려주었기 때문에 그 장소로 가능한 한 빨리 가려고 한다. 놀이동산은  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,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에 대해서 해인이의 현재 위치에서 목표 위치까지 가는데 필요한 최소 시간을 출력하라.

예제 입력

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

예제 출력

3 1

힌트