岛屿题

题号：NC282851
时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

题目背景

时间紧任务重这是只有二十八字的题目背景我花五秒钟就写完了。

题目描述

给你一张 $n$ 行 $m$ 列的地图，每个点可能是 '#','.' 和 'v' 三种状态，分别表示岛屿，空地与火山。
现在有 $q$ 次询问，每次询问给你一个 $(x,y)$ ，询问从 $(x,y)$ 出发再回到 $(x,y)$ ，把所有岛屿围起来，路径权值最大是多少，
我们定义一条路径合法，当且仅当他的每一步都不走出地图边界，不经过岛屿（特别地，火山是可以经过的），同时相邻两步的横坐标与纵坐标必然有一个相同另一个差 $1$ ，注意这里并不要求这条路径不走回头路或是不走走过的路。
而我们定义一条路径的权值为路径中每一个点到火山的曼哈顿距离的最小值。

多组数据。

注意可能有多个不联通的岛屿，你必须把他们全部围起来，具体地，假设把路径经过的点全部删除，没有任何一个岛屿点与没有被删除的边界八联通。

数据范围

$1\leqslant T\leqslant 10^4, 1\leqslant n,m\leqslant 1000,\sum nm\leqslant 10^6,1\leqslant q\leqslant 10^6,\sum q \leqslant 10^6,1\leqslant x\leqslant n,1\leqslant y\leqslant m$ ，数据保证至少存在一种从 $(x,y)$ 出发环所有岛屿一圈的方案，同时 $(x,y)$ 必然在空地。

输入描述:

第一行，一个整数 ，表示数据组数。
对于每组数据：
第一行，三个正整数 ，分别表示地图的行列数与询问次数。
接下来  行，每行  个字符，表示输入地图。
接下来  行，每行两个正整数 ，表示询问的起点的位置。

输出描述:

对于每组数据：
 行，每行一个整数表示从  出发再回到  并围起所有岛屿的最大路径权值。

示例1

输入

复制

1
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7

输出

复制

3
0
3

示例2

输入

复制

1
3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2

输出

复制

示例3

输入

复制

1
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

输出

复制

示例4

输入

复制

1
10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1

输出

复制

示例5

输入

复制

1
10 10 1
..........
..........
...#.#.#..
....#v#v..
...v.##v..
v...vv...v
..#v...#..
.....v.v..
...v..v...
..v.......
2 3

输出

复制

示例6

输入

复制

1
10 10 1
.v........
.v........
......#...
..v....#..
....v.....
..........
..#.......
.....v....
........v.
..........
5 10

输出

复制