← 返回题目列表

AtCoder · pakencamp_2019_day3_e

E. 圣诞大礼物

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

配点: 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 广场内没有建筑物。

部分点

该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (13 点) H = 1,W \leq 200,Q = 1 ,当前的一侧的长度 L_i 就是全部 1 。
  2. (13 点) H \leq 200,W \leq 200,Q = 1 ,当前的一侧的长度 L_i 就是全部 1 。
  3. (19 分) 礼物一侧的长度 L_i 就是全部 1 。
  4. (11 点) H \leq 200,W \leq 200,Q = 1 。
  5. (11 点) H \leq 200,W \leq 200,Q \leq 1 \ 000 。
  6. (11 点) H \leq 200,W \leq 200 。
  7. (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