CF1920F1 Smooth Sailing (Easy Version)

本题的两个版本唯一的区别在于 $q$ 的限制。只有当两个版本都被解决时，你才能进行 Hack。 Thomas 正在环绕一个被海洋包围的岛屿航行。海洋和岛屿可以用一个有 $n$ 行 $m$ 列的网格表示。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $r$ 行第 $c$ 列的格子可以表示为 $(r, c)$。下面是一个合法网格的示例。  合法网格示例 网格中有三种类型的格子：岛屿、海洋和海底火山。岛屿格子用 '\#' 表示，海洋格子用 '.' 表示，海底火山格子用 'v' 表示。保证至少有一个岛屿格子和至少一个海底火山格子。还保证所有岛屿格子构成一个连通块 $^{\dagger}$，所有海洋格子和海底火山格子构成一个连通块。此外，保证网格的边界（即第 $1$ 行、第 $n$ 行、第 $1$ 列和第 $m$ 列）上没有岛屿格子。 定义从格子 $(x, y)$ 出发的“环岛航行”为一条满足以下条件的路径： - 路径从 $(x, y)$ 出发，最终回到 $(x, y)$。 - 如果 Thomas 当前在格子 $(i, j)$，他可以移动到 $(i+1, j)$、$(i-1, j)$、$(i, j-1)$、$(i, j+1)$，只要目标格子是海洋格子或海底火山格子且仍在网格内。注意，在一次环岛航行中，允许多次经过同一个格子。 - 路径必须环绕岛屿并将其完全包围。某条路径 $p$ 被认为完全包围了岛屿，当且仅当无法从任意岛屿格子仅通过相邻的边或对角线格子（不经过路径 $p$ 上的格子）到达网格边界。下图中，从 $(2, 2)$ 出发，经过 $(1, 3)$，再从另一条路返回 $(2, 2)$ 的路径没有完全包围岛屿，因此不算作一次环岛航行。  未完全包围岛屿的路径示例 一次环岛航行的“安全性”定义为路径上某个格子到最近海底火山的曼哈顿距离 $^{\ddagger}$ 的最小值（注意岛屿格子的存在不影响该距离的计算）。 你有 $q$ 个询问。每个询问为 $(x, y)$，对于每个询问，你需要求出从 $(x, y)$ 出发的环岛航行的最大安全性。保证 $(x, y)$ 是海洋格子或海底火山格子。 $^{\dagger}$ 一组格子构成一个连通块，指的是从该集合中的任意一个格子出发，仅通过该集合中的格子、每次移动到有公共边的格子，可以到达集合中的任意另一个格子。 $^{\ddagger}$ 格子 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的曼哈顿距离为 $|r_1 - r_2| + |c_1 - c_2|$。

第一行包含三个整数 $n$、$m$ 和 $q$（$3 \leq n, m \leq 10^5$，$9 \leq n \cdot m \leq 3 \cdot 10^5$，$1 \leq q \leq 5$），分别表示网格的行数、列数和询问数。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述网格中的格子。字符 '\#' 表示岛屿格子，'.' 表示海洋格子，'v' 表示海底火山格子。 保证至少有一个岛屿格子和至少一个海底火山格子。保证所有岛屿格子构成一个连通块，所有海洋格子和海底火山格子构成一个连通块。还保证网格的边界（即第 $1$ 行、第 $n$ 行、第 $1$ 列和第 $m$ 列）上没有岛屿格子。 接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x \leq n$，$1 \leq y \leq m$），表示一次从 $(x, y)$ 出发的环岛航行。 保证 $(x, y)$ 是海洋格子或海底火山格子。

对于每个询问，输出一个整数，表示从指定位置出发的环岛航行的最大安全性。

对于第一个样例，下图展示了从 $(1, 1)$ 出发的最优环岛航行。该环岛航行的安全性为 $3$，因为路径上某个格子到最近海底火山的曼哈顿距离为 $3$。  最优环岛航行示例 对于第四个样例，注意在一次环岛航行中允许多次经过同一个格子。例如，从 $(7, 6)$ 出发的环岛航行就必须这样做。 由 ChatGPT 4.1 翻译