Chủ tịch K thích giải mê cung. Ông tìm thấy một bảng ô vuông có thể dùng để tạo mê cung. Bảng có dạng hình chữ nhật gồm \(R\) hàng và \(C\) cột, mỗi ô được tô màu trắng hoặc đen. Gọi ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le R\)), cột thứ \(j\) từ trái sang (\(1 \le j \le C\)) là ô \((i, j)\).

Chủ tịch K quy định chỉ được đi qua các ô trắng, không được đi qua các ô đen. Cụ thể, ông chọn hai ô trắng: ô xuất phát \((S_r, S_c)\) và ô đích \((G_r, G_c)\). Mỗi bước được chuyển sang một ô trắng kề ô hiện tại theo một trong bốn hướng trên, dưới, trái, phải. Mục tiêu là tìm đường từ ô xuất phát đến ô đích bằng cách lặp lại các bước như vậy.

Sau khi đã chọn cố định ô xuất phát và ô đích, chủ tịch K nhận ra rằng, tùy cách tô màu của bảng, có thể không tồn tại đường đi chỉ qua các ô trắng nối hai ô này. Ông có một con dấu kích thước \(N \times N\) ô và muốn thực hiện thao tác sau một số lần để tạo ra một đường đi như vậy.

Trong mỗi thao tác, chọn một vùng hình vuông gồm \(N \times N\) ô nằm trong bảng và tô trắng tất cả các ô thuộc vùng đó. Cụ thể, chọn hai số nguyên \(a, b\) thỏa mãn \(1 \le a \le R - N + 1\) và \(1 \le b \le C - N + 1\). Với mọi cặp số nguyên \((i, j)\) thỏa mãn \(a \le i \le a + N - 1\) và \(b \le j \le b + N - 1\), tô ô \((i, j)\) thành màu trắng.

Vì dùng con dấu có thể làm bẩn tay, chủ tịch K muốn số thao tác ít nhất có thể. Cho màu của các ô, kích thước con dấu, ô xuất phát và ô đích, hãy tìm số thao tác nhỏ nhất cần thực hiện để có đường đi từ ô xuất phát đến ô đích chỉ qua các ô trắng.

Dữ liệu vào

Dữ liệu vào có dạng:

R C N
S_r S_c
G_r G_c
A_1
A_2
...
A_R

\(A_i\) (\(1 \le i \le R\)) là xâu có độ dài \(C\), chỉ gồm các ký tự . và #. Ký tự thứ \(j\) (\(1 \le j \le C\)) của \(A_i\) biểu diễn màu của ô \((i, j)\): . là màu trắng, còn # là màu đen.

Dữ liệu ra

In trên một dòng số thao tác nhỏ nhất cần thực hiện để có đường đi từ ô xuất phát đến ô đích chỉ qua các ô trắng.

Ràng buộc

• \(1 \le N \le R \le C\).
• \(R \times C \le 6\,000\,000\).
• \(1 \le S_r \le R\).
• \(1 \le S_c \le C\).
• \(1 \le G_r \le R\).
• \(1 \le G_c \le C\).
• \((S_r, S_c) \ne (G_r, G_c)\).
• \(A_i\) (\(1 \le i \le R\)) là xâu có độ dài \(C\), chỉ gồm . và #.
• Ô \((S_r, S_c)\) có màu trắng.
• Ô \((G_r, G_c)\) có màu trắng.
• \(R, C, N, S_r, S_c, G_r, G_c\) là các số nguyên.

Chấm điểm

1. \(8\) điểm: \(N = 1\), \(R \times C \le 1\,500\,000\).
2. \(19\) điểm: \(R \times C \le 1000\).
3. \(16\) điểm: Đáp án không vượt quá \(10\) và \(R \times C \le 1\,500\,000\).
4. \(19\) điểm: \(R \times C \le 60\,000\).
5. \(5\) điểm: \(R \times C \le 150\,000\).
6. \(19\) điểm: \(R \times C \le 1\,500\,000\).
7. \(8\) điểm: \(R \times C \le 3\,000\,000\).
8. \(6\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

1

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

4

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

1

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

0

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.