AT_abc260_g [ABC260G] Scalene Triangle Area

题目描述

有一个 $N \times N$ 的网格，我们称从上往下第 $i$ 行，从左往右第 $j$ 列的格子为 $(i,j)$。
每个格子上至多放有 $1$ 个棋子。
网格的状态由 $N$ 个字符串 $S_i$ 给出：

• 当 $S_i$ 的第 $j$ 个字符为 O 时，表示 $(i,j)$ 上有 $1$ 个棋子；
• 当 $S_i$ 的第 $j$ 个字符为 X 时，表示 $(i,j)$ 上没有棋子。

给定整数 $M$。对于放在 $(s,t)$ 的棋子 $P$，定义 $P$ 能“守护”的格子 $(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$
$S_1$
$S_2$
$\vdots$
$S_N$
$Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

输出格式

输出 $Q$ 行。
第 $i$ 行输出格子 $(X_i, Y_i)$ 被守护的棋子数量。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

输入 #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

说明/提示

数据范围

• $N, M, X_i, Y_i, Q$ 为整数
• $1 \le N \le 2000$
• $1 \le M \le 2N$
• $S_i$ 只包含 O 和 X
• $1 \le Q \le 2 \times 10^5$
• $1 \le X_i, Y_i \le N$

样例解释 1

只有 $(1,1)$ 有棋子，该棋子能守护如下用 # 表示的格子：

####
##..
....
....

由 ChatGPT 4.1 翻译