← 返回题目列表

Codeforces · 598/D

D. 伊戈尔在博物馆

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

伊戈尔在博物馆里,他想看尽可能多的照片。

博物馆可以表示为一个由 n × m 个单元组成的矩形区域。每个牢房要么是空的,要么是无法通行的。空单元格用“.”标记,不可通过的单元格用“*”标记。每两个不同类型的相邻牢房(一个是空的,一个是不可通行的)被一面包含一张图片的墙隔开。

一开始,伊戈尔在某个空牢房里。他随时都可以移动到与当前单元格共享一侧的任何空单元格。

对于几个起始位置,您应该计算 Igor 可以看到的最大图片数量。只有当伊戈尔位于靠近有这张照片的墙壁的牢房中时,他才能看到这张照片。伊戈尔有很多时间,所以他会检查他能看到的每一张图片。

输入

输入的第一行包含三个整数 n、m 和 k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) - 博物馆尺寸和要处理的起始位置的数量。

接下来的 n 行每一行都包含 m 个符号“.”、“*”——博物馆的描述。保证所有边境牢房都无法通行,所以伊戈尔无法走出博物馆。

最后 k 行中的每一行包含两个整数 x 和 y (1 ≤ x ≤ n, 1 ≤ y ≤ m)——分别是 Igor 起始位置之一的行和列。行从上到下编号,列从左到右编号。保证所有起始位置都是空单元格。

输出

打印 k 个整数 — 如果 Igor 从相应的位置开始,他可以看到的最大图片数。

示例

输入 #1

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

输出 #1

6
4
10

输入 #2

4 4 1
****
*..*
*.**
****
3 2

输出 #2

8