놀이공원
시간 제한2초메모리 제한128 MB
각 칸에 들어갈 때마다 1/C만큼 비용이 들고 1분 구간 동안 누적 비용이 1을 넘지 못하는 규칙에서 출발지에서 목적지까지 걸리는 최소 시간을 구하는 문제입니다.
문제
해인이는 N x M 격자로 이루어진 놀이공원에서 친구들과 헤어졌다. 격자의 맨 왼쪽 위 칸은 (1, 1), 맨 오른쪽 아래 칸은 (N, M)이다.
각 칸 (i, j)에는 양의 정수 Cij가 적혀 있고, 그 칸을 한 번 지나가는 비용은 1/Cij이다. 해인이는 현재 칸에서 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 즉시 이동할 수 있으므로, 이동 자체에는 시간이 들지 않는다.
시간은 0분부터 1분, 1분부터 2분, 2분부터 3분처럼 1분 단위 구간으로 나뉜다. 한 구간 안에서 해인이가 지나간 칸들의 비용 합은 1 이하여야 한다. 구간이 바뀌면 비용 합은 새로 계산되며, 새 구간을 시작하는 현재 칸도 그 구간에서 지나간 칸에 포함된다.
시작 위치 (Sx, Sy), 목적지 (Dx, Dy), 행렬 C가 주어질 때, 해인이가 시작 위치에서 목적지까지 도착하는 데 필요한 최소 시간을 구하여라.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 격자의 크기 N, M이 주어진다. (1 <= N, M <= 50)
다음 N줄에는 행렬 C가 주어진다. 각 줄은 공백 없이 M개의 숫자로 이루어져 있으며, j번째 숫자는 해당 행의 Cij이다.
마지막 줄에는 네 정수 Sx, Sy, Dx, Dy가 주어진다. (1 <= Sx, Dx <= N, 1 <= Sy, Dy <= M)
출력
각 테스트 케이스마다 시작 위치에서 목적지까지 도착하는 데 필요한 최소 시간을 한 줄에 출력한다. 도착할 수 없으면 -1을 출력한다. 이미 목적지에 있다면 0을 출력한다.