← 返回题目列表

Codeforces · 1920/F2

F2. 一帆风顺(困难版)

中文机器翻译题面 查看原题

这个问题的两个版本之间的唯一区别是对 $$$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 3 \cdot 10^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)$$$ 开始的往返行程,必须这样做。