Cho một lưới \(n\times n\), mỗi ô là đất hoặc nước. Các hàng và cột được đánh số từ \(1\) đến \(n\). Mỗi bước, bạn có thể đi sang trái, sang phải, lên hoặc xuống. Hai ô được gọi là liên thông nếu có thể đi giữa chúng qua một hoặc nhiều bước mà luôn ở trên các ô cùng loại.

Các ô đất tạo thành một hòn đảo liên thông và các ô nước tạo thành một đại dương liên thông. Hàng đầu, hàng cuối, cột đầu và cột cuối chỉ gồm các ô nước.

Bạn cần trả lời \(q\) truy vấn. Với hai ô đất \((r_1,c_1)\) và \((r_2,c_2)\), hãy tìm số bước ít nhất để đi từ ô thứ nhất tới ô thứ hai mà luôn ở trên đất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,q\), lần lượt là kích thước lưới và số truy vấn.

\(n\) dòng tiếp theo, mỗi dòng gồm \(n\) ký tự mô tả lưới. Ký tự . biểu diễn nước và # biểu diễn đất.

\(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(r_1,c_1,r_2,c_2\), mô tả hàng và cột của hai ô đất.

Dữ liệu ra

Với mỗi truy vấn, in đáp án trên một dòng riêng.

Ràng buộc

• \(3\le n\le1000\).
• \(1\le q\le10^5\).
• Trong mọi truy vấn, \(1<r_1,c_1,r_2,c_2<n\).

Phân nhóm

1. \(10\) điểm: \(n\le200\), \(q\le200\).
2. \(6\) điểm: trên mỗi hàng và mỗi cột, không có ô nước nào nằm giữa hai ô đất.
3. \(16\) điểm: không có hình vuông \(2\times2\) nào gồm toàn ô đất.
4. \(28\) điểm: trên mỗi hàng, không có ô nước nào nằm giữa hai ô đất.
5. \(40\) điểm: không có ràng buộc thêm.

8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2

5
0
17
3

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.