달리기

면접 대비

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

요약

벽이 있는 격자에서 한 번에 상하좌우로 빈 칸을 1칸 이상 K칸 이하 이동할 때, 시작점에서 도착점까지 가는 최소 이동 횟수를 구한다.

문제

진영이는 다이어트를 위해 $N \times M$ 크기의 체육관을 달리려고 한다. 체육관은 $1 \times 1$ 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. $x$ 행 $y$ 열에 있는 칸은 $(x, y)$ 로 나타낸다.

매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 $K$ 개의 빈 칸을 이동한다.

시작점 $(x_1, y_1)$ 과 도착점 $(x_2, y_2)$ 가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간을 구해보자.

첫째 줄에 체육관의 크기 $N$ 과 $M$ , 1초에 이동할 수 있는 칸의 최대 개수 $K$ 가 주어진다.

둘째 줄부터 $N$ 개의 줄에는 체육관의 상태가 주어진다. 체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 '.', 벽은 '#'으로 주어진다.

마지막 줄에는 네 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 주어진다. 두 칸은 서로 다른 칸이고, 항상 빈 칸이다.

$(x_1, y_1)$ 에서 $(x_2, y_2)$ 로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.