문제
명장 승민 장군은 전장의 적들을 뚫고 도착점에 도달하라는 명령을 받았다.
전장은 R * C 크기의 격자판 형태이다.
격자판 내 '#'은 적이 존재하는 구역이며, '.'은 이동 가능한 구역으로 주어진다.
이동은 상하좌우 한 칸씩 이동 가능하다.
승민 장군은 많은 전투로 힘을 다 써서 적들을 이길 수 없다.
따라서 폭격 명령을 통해 적들을 제거 후 도착점에 도달하고자 한다.
폭격 명령 : 전장 중 일부 N * N 구역에 있는 적들을 전부 제거한다.
즉, N * N 구역에 존재하는 모든 '#'을 '.'으로 변경한다.
( N * N 구역은 전부 전장 내에 존재해야 하며, 승민 장군은 엄청난 회피 능력으로 폭격에서 살아남는다. )
도착점에 도달하기 위한 최소 폭격 명령 횟수를 구하라.
입력
첫 줄에 전장의 크기인 행 R, 열 C, 폭격 구역의 크기 N이 공백을 구분으로 주어진다.
다음 줄에 출발점 SR, SC 가 공백을 구분으로 주어진다.
다음 줄에 도착점 GR, GC 가 공백을 구분으로 주어진다.
이후 전장 정보가 R줄에 걸쳐 이동 가능한 구역'.' 또는 적이 존재하는 구역'#' 문자가 공백없이 C개씩 주어진다.
[제약 조건]
1 ≤ N ≤ R ≤ C
R * C ≤ 6,000,000
전장은 '#'과 '.'으로만 이루어져 있다.
출발점과 도착점은 전장 내에 존재하며 서로 다르다. 또한 출발점과 도착점은 '.'이 보장된다.
모든 입력은 정수다.
출력
도착점에 도달하기 위해 내려야 할 최소 폭격 명령 횟수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | N = 1, R * C ≤ 1,500,000 |
| #2 | 19점 | R * C ≤ 1,000 |
| #3 | 16점 | 답은 10이하, R * C ≤ 1,500,000 |
| #4 | 19점 | R * C ≤ 60,000 |
| #5 | 5점 | R * C ≤ 150,000 |
| #6 | 19점 | R * C ≤ 1,500,000 |
| #7 | 8점 | R * C ≤ 3,000,000 |
| #8 | 6점 | 추가 제약 조건 없음. |
예제1
242
11
24
.###
###.
1
예제2
661
16
61
..#.#.
##.###
####.#
...###
##.##.
.#.###
4
예제3
676
64
31
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.
1
예제4
1151
115
11
...............
0