配点: 100 点
問題文
PAKEN城市从北向南延伸。 H 米,从东到西 W 它的形状为一米长方形。这是南北 1 从东到西米 1 相隔米 从北边开始,它被分为 H \times W 个方格。 i 个,从西边算起 第 j 广场 我们将其表示为 (i, j) 。
PAKEN城的一些广场有建筑物,不能通过,其他广场是可以通行的广场。更具体地说,S_{i, j} 是
在 # 表示建筑物已建成且无法通过,. 表示道路可以通行。
圣诞老人E869120,你将给公园王国送一份礼物。 我决定将其分发 Q 次。
i 首次礼物发放如下。
- 一、质量 (X_i, Y_i) 是左上角的正方形,一侧是 L_i 有一个一米见方的礼物。
- 然后您可以移动礼物。更具体地说,“不要旋转礼物,以免它与建筑物重叠,而是将其精确地放置在任一方向,北,南,东或西。 1 多次移动仪表(0 次)。
但是,请不要以可能导致部分礼物出现在 PAKEN 市以外的方式离开 PAKEN 市。
找出每次礼物分配可能的最终礼物位置的数量。
制約
- 1 \leq H \leq 1 \ 500
- 1 \leq W \leq 1 \ 500
- 1 \leq Q \leq 150 \ 000
- H, W, Q 均为整数
- Q 所有礼物的初始位置都在PAKEN City内,并且 L_i^2 广场内没有建筑物。
部分点
该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (13 点) H = 1,W \leq 200,Q = 1 ,当前的一侧的长度 L_i 就是全部 1 。
- (13 点) H \leq 200,W \leq 200,Q = 1 ,当前的一侧的长度 L_i 就是全部 1 。
- (19 分) 礼物一侧的长度 L_i 就是全部 1 。
- (11 点) H \leq 200,W \leq 200,Q = 1 。
- (11 点) H \leq 200,W \leq 200,Q \leq 1 \ 000 。
- (11 点) H \leq 200,W \leq 200 。
- (22 分) 没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
H W
S_{1, 1} S_{1, 2} S_{1, 3} \cdots S_{1, W}
S_{2, 1} S_{2, 2} S_{2, 3} \cdots S_{2, W}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, W}
: : :
S_{H, 1} S_{H, 2} S_{H, 3} \cdots S_{H, W}
Q
X_1 Y_1 L_1
X_2 Y_2 L_2
X_3 Y_3 L_3
: :
X_Q Y_Q L_Q
出力
从第一次礼物分配开始,计算最终可能的礼物位置的数量。1 请逐行输出。
入力例 1
1 10 .#..##...# 1 1 7 1
出力例 1
3
此输入示例满足子任务 1 的约束。
现在如下,包括初始位置。 3 它可以移动到两个位置。

入力例 2
6 5 #..#. ..#.. #.#.. ..#.. .#..# .#... 1 3 4 1
出力例 2
12
此输入示例满足子任务 2 的约束。
现在是 解决 12 它可以移动到两个位置。
入力例 3
8 8 ....#... ..#..... ......#. #....... ...#.... .#...... .....#.. .......# 6 4 5 1 1 6 2 2 5 2 7 1 2 4 6 3 6 3 3
出力例 3
56 2 14 6 2 1