← 返回题目列表

AtCoder · abc260_g

G. 不等边三角形面积

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

分数: 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