#5713. 「BalticOI 2026」岛屿

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2026 Day1「Island」

给定一个 $n \times n$ 的网格，每个格子要么是陆地，要么是水域。网格的行和列编号分别为 $1, 2, \ldots, n$。你可以在网格中向左、右、上、下移动。若两个格子可以通过同类型的格子连接，且在移动过程中始终停留在同类型的格子中，则称这两个格子是连通的。

陆地格子构成一个连通的岛屿，水域格子构成一个连通的海洋。网格的第一行、最后一行、第一列和最后一列仅包含水域格子。

你的任务是回答 $q$ 个询问：给定两个陆地格子 ($r_{1}, c_{1}$) 和 ($r_{2}, c_{2}$)，求出从第一个格子移动到第二个格子的最少步数，且移动过程中必须始终在陆地上。

输入格式

第一行包含两个整数 $n$ 和 $q$：网格的大小和询问次数。

接下来 $n$ 行，每行包含 $n$ 个字符，用于描述网格。. 表示水域格子，# 表示陆地格子。

接下来 $q$ 行，每行包含四个整数 $r_{1}, c_{1}, r_{2}$ 和 $c_{2}$：第一个格子的行号和列号，以及第二个格子的行号和列号。

输出格式

对于每个询问，输出一行答案。

样例

输入

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

输出

5
0
17
3

数据范围与提示

对于所有输入数据，满足：

• $3 \leq n \leq 1000$
• $1 \leq q \leq 10^{5}$
• 在所有询问中，$1 < r_{1}, c_{1}, r_{2}, c_{2} < n$

详细子任务附加限制及分值如下表所示。