分数: 600 点
问题陈述
我们有一个 N \times N 网格。 广场位于 i从顶部开始的第行和 j该网格中从左侧算起的第列称为 (i,j).
网格的每个方格最多有一个棋子。
网格状态由下式给出 N 字符串 S_i:
- 如果 j- 第一个字符 S_i is
O,那么 (i,j) 上面有一块; - 如果 j- 第一个字符 S_i is
X,那么 (i,j) 上没有任何内容。
给你一个整数 M。 使用这个 M,我们定义一块 P 放置于 (s,t) 覆盖一个正方形 (u,v) 如果满足以下所有条件:
- s \le u \le N
- t \le v \le N
- (u - s) + \frac{(v - t)}{2} < M
对于每个 Q 方块 (X_i,Y_i),找出有多少块覆盖了正方形。
约束
- N, M, X_i, Y_i,和 Q 是整数。
- 1 \le N \le 2000
- 1 \le M \le 2 \times N
- S_i 包括
O和X. - 1 \le Q \le 2 \times 10^5
- 1 \le X_i,Y_i \le N
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
输出
打印 Q 行。
的 i- 第行 ( 1 \le i \le Q ) 应包含覆盖的件数 (X_i,Y_i) 作为整数。
样本输入 1
4 2 OXXX XXXX XXXX XXXX 6 1 1 1 4 2 2 2 3 3 1 4 4
示例输出 1
1 1 1 0 0 0
仅正方形 (1,1) 包含一段内容,涵盖以下内容 # 方块:
#### ##.. .... ....
示例输入 2
5 10 OOOOO OOOOO OOOOO OOOOO OOOOO 5 1 1 2 3 3 4 4 2 5 5
示例输出 2
1 6 12 8 25
示例输入 3
8 5 OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO 6 7 2 8 1 4 5 8 8 3 4 1 7
示例输出 3
5 3 9 14 5 3