题目描述

给定一个 $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$，依次表示第一个格子的行、列，以及第二个格子的行、列。

输出格式

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

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

5
0
17
3

提示

数据范围

• $3\le n\le 1000$
• $1\le q\le 10^5$
• 所有询问满足 $1 < r_1,c_1,r_2,c_2 < n$

子任务

翻译由 DeepSeek V4 Pro 完成