시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB416635.294%

## 문제

President K loves solving mazes. He found cells from which he may create a maze. The cells are rectangular grid with $R$ horizontal rows and $C$ vertical columns. Each cell is colored either white or black. The cell in the $i$-th row ($1 ≤ i ≤ R$) from the top and the $j$-th column ($1 ≤ j ≤ C$) from the left is called Cell $(i, j)$.

President K will solve the maze under the condition that he can pass the white cells, but he cannot pass the black cells. More precisely, he will solve the maze in the following way.

1. Among the white cells, he will choose Cell $(S_r, S_c)$, which is the starting cell of the maze, and Cell $(G_r, G_c)$, which is the goal cell of the maze.
2. It is possible to move from one cell to another white cell which is adjacent to the current cell in one of the four directions (top, bottom, left, or right). By repeating this, he will find a path from the starting cell to the goal cell.

President K already fixed the starting cell and the goal cell. However, he noticed that in some situations of the colors of the cells, there might not be a path from the starting cell to the goal cell consisting of white cells only. He has a stamp of size $N \times N$. He will perform the following Operations several times so that there will be a path from the starting cell to the goal cell consisting of white cells only.

Operation He chooses a square region of $N \times N$ cells, and paint the cells in the region white. More precisely, he chooses integers $a$, $b$ satisfying $1 ≤ a ≤ R - N + 1$ and $1 ≤ b ≤ C - N + 1$, and for every pair $(i, j)$ of integers satisfying $a ≤ i ≤ a + N - 1$ and $b ≤ j ≤ b + N - 1$, he paints Cell $(i, j)$ white.

Since his hands becomes dirty if he uses the stamp, he wants to minimize the number of operations. Given information of the colors of the cells, the size of the stamp, and the locations of the starting cell and the goal cell, write a program which calculates the minimum number of operations he has to perform so that there will be a path from the starting cell to the goal cell consisting of white cells only.

## 입력

Read the following data from the standard input.

$R$ $C$ $N$

$S_r$ $S_c$

$G_r$ $G_c$

$A_1$

$A_2$

$\vdots$

$A_R$

$A_i$ ($1 ≤ i ≤ R$) is a string of length $C$ consisting of . or #. The $j$-th character ($1 ≤ j ≤ C$) of $A_i$ represents the color of Cell $(i, j)$. Its color is white if the character is ., and its color is black if the character is #.

## 출력

Write one line to the standard output. The output should contain the minimum number of operations President K has to perform so that there will be a path from the starting cell to the goal cell consisting of white cells only.

## 제한

• $1 ≤ N ≤ R ≤ C$.
• $R \times C ≤ 6\,000\,000$.
• $1 ≤ S_r ≤ R$.
• $1 ≤ S_c ≤ C$.
• $1 ≤ G_r ≤ R$.
• $1 ≤ G_c ≤ C$.
• $(S_r , S_c) \ne (G_r ,G_c)$.
• $A_i$ ($1 ≤ i ≤ R$) is a string of length $C$ consisting of . or #.
• The color of Cell $(S_r , S_c)$ is white.
• The color of Cell $(G_r ,G_c)$ is white.
• $R$, $C$, $N$, $S_r$, $S_c$, $G_r$, $G_c$ are integers.

## 서브태스크

번호배점제한
18

$N = 1$, $R \times C ≤ 1\,500\,000$.

219

$R \times C ≤ 1\,000$.

316

The answer is less than or equal to $10$, and $R \times C ≤ 1\,500\,000$.

419

$R \times C ≤ 60\,000$.

55

$R \times C ≤ 150\,000$.

619

$R \times C ≤ 1\,500\,000$.

78

$R \times C ≤ 3\,000\,000$.

86

## 예제 입력 1

2 4 2
1 1
2 4
.###
###.


## 예제 출력 1

1


If he chooses $(a, b) = (1, 2)$ and perform an operation, Cells $(1, 2)$, $(1, 3)$, $(2, 2)$, $(2, 3)$ become white. Then there will be a path from the starting cell to the goal cell consisting of white cells only. For example, the path $(1, 1) → (1, 2) → (1, 3) → (2, 3) → (2, 4)$ satisfies the condition.

If he does not perform an operation, there is no path from the starting cell to the goal cell consisting of white cells only. Therefore, output $1$.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.

## 예제 입력 2

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###


## 예제 출력 2

4


This sample input satisfies the constraints of all the subtasks.

## 예제 입력 3

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.


## 예제 출력 3

1


This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.

## 예제 입력 4

1 15 1
1 15
1 1
...............


## 예제 출력 4

0


Even if he does not perform an operation, there might be a path from the starting cell to the goal cell consisting of white cells only.

This sample input satisfies the constraints of all the subtasks.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.