P16358 [BalticOI 2026] Island

给定一个 $n\times n$ 的网格，每个格子要么是陆地，要么是水域。网格的行和列均从 $1$ 到 $n$ 编号。你可以在网格中向左、右、上、下一步移动。如果在移动过程中始终停留在同一种类型的格子上，则称这两个格子是连通的。 所有陆地格子构成一个连通的岛屿，而所有水域格子构成一个连通的海洋。网格的第一行、最后一行、第一列和最后一列均只包含水域格子。 你的任务是回答 $q$ 个询问：给定两个陆地格子 $(r_1,c_1)$ 和 $(r_2,c_2)$，从第一个格子出发，在只经过陆地格子的前提下，到达第二个格子所需的最少步数是多少？

第一行包含两个整数 $n$ 和 $q$，分别表示网格的大小和询问的数量。 接下来 $n$ 行，每行包含 $n$ 个字符，描述整个网格。其中 "`.`" 表示水域格子，"`#`" 表示陆地格子。 再接下来 $q$ 行，每行包含四个整数 $r_1$, $c_1$, $r_2$ 和 $c_2$，依次表示第一个格子的行、列，以及第二个格子的行、列。

对于每个询问，输出一行一个整数表示答案。

### 数据范围 - $3\le n\le 1000$ - $1\le q\le 10^5$ - 所有询问满足 $1 < r_1,c_1,r_2,c_2 < n$ ### 子任务 | 子任务 | 约束条件 | 分值 | | :---: | --- | :---: | | 1 | $n \le 200$, $q \le 200$ | $10$ | | 2 | 没有一行或一列在陆地格子之间存在水域格子 | $6$ | | 3 | 不存在任何 $2\times2$ 的区域全为陆地格子 | $16$ | | 4 | 没有一行在陆地格子之间存在水域格子 | $28$ | | 5 | 无额外限制 | $40$ | 翻译由 DeepSeek V4 Pro 完成