这个问题的两个版本之间的唯一区别是对 $$$q$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
托马斯正在围绕一个被海洋包围的岛屿航行。海洋和岛屿可以用具有 $$$n$$$ 行和 $$$m$$$ 列的网格来表示。行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$m$$$。行 $$$r$$$ 和列 $$$c$$$ 的单元格位置可以表示为 $$$(r, c)$$$。以下是有效网格的示例。
有效网格示例
细胞分为三种类型:岛屿、海洋和水下火山。代表岛屿的单元格用“#”标记,代表海洋的单元格用“.”标记,代表水下火山的单元格用“v”标记。保证至少有1个岛屿细胞和至少1个水下火山细胞。还保证所有岛屿单元的集合形成单个连通分量$$$^{\dagger}$$$,所有海洋单元和水下火山单元的集合形成单个连通分量。此外,还保证网格边缘(即,行 $$$1$$$、行 $$$n$$$、列 $$$1$$$ 和列 $$$m$$$ 处没有岛状单元。
定义从单元格 $$$(x, y)$$$ 开始的往返行程作为 Thomas 所采用的路径,该路径满足以下条件:
- 路径的起点和终点为 $$$(x, y)$$$。
- 如果 Thomas 位于单元格 $$$(i, j)$$$,则只要目标单元格是海洋单元格或水下火山单元格且仍在网格内,他就可以前往单元格 $$$(i+1, j)$$$、$$$(i-1, j)$$$、$$$(i, j-1)$$$ 和 $$$(i, j+1)$$$。请注意,允许 Thomas 在同一次往返中多次访问同一单元。
- 路径必须绕过岛屿并完全包围它。如果仅通过移动到一侧或对角线上的相邻单元而不访问路径 $$$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
9 9 3 ......... ......... ....###.. ...v#.... ..###.... ...##...v ...##.... ......... v........ 1 1 9 1 5 7
输出 #1
3 0 3
输入 #2
3 3 5 ..v .#. ... 1 2 1 3 2 3 2 1 3 2
输出 #2
0 0 0 0 0
输入 #3
14 13 5 ............. ............. ............. ...vvvvvvv... ...v.....v... ...v.###.v... ...v.#.#.v... ...v..v..v... ...v..v..v... ....v...v.... .....vvv..... ............. ............. ............. 1 1 7 7 5 6 4 10 13 6
输出 #3
3 0 1 0 2
输入#4
10 11 4 ........... ..#######.. ..#..#..#.. ..#.....#.. ..#..v..#.. ..#.###.#.. ..#.#.#.#.. ..#...#.#.. ..#####.#.. ........... 7 6 3 7 6 8 1 1
输出#4
1 2 3 4
注意
对于第一个示例,下图显示了从 $$$(1, 1)$$$ 开始的最佳往返行程。往返的安全性为 $$$3$$$,因为从单元到水下火山往返的最小曼哈顿距离为 $$$3$$$。
最佳往返示例
对于第四个示例,请记住,允许 Thomas 在同一次往返中多次访问同一单元格。例如,对于从 $$$(7, 6)$$$ 开始的往返行程,必须这样做。