← 返回题目列表

AtCoder · nadafes2022_day2_c

C. 定时炸弹

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

配点 : 400 点

問題文

kentand 将拆除炸弹。 有一个

H×W 正方形,从顶部 i \lparen 1 \le i \le H \rparen 行,从左起 j \lparen 1 \le j \le W \rparen 柱方 当 \lparen i,j\rparen 满足 G_{i,j} 是 # 在墙上时,. 是道路。

广场上方的道路上有一枚炸弹。 N 可用, k \lparen 1 \le k \le N \rparen 第二颗炸弹是方形的 它位于 \lparen C_k, D_k \rparen 。

肯坦德 是时候 0 到质量 \lparen 1,1 \rparen 闻,1 对于每个时间单位,移动到道路上与您当前所在的广场在上、下、左、右方向相邻的广场。也可以移动到带有炸弹的方格。你们不能呆在同一个广场上。

并且,k 在炸弹所在的广场 你可以随时进入 S_k,S_k+1,\ldots,T_k 来拆除炸弹。释放所需的时间可以忽略不计。

如果你行动得当,你能拆除多少炸弹?

制約

  • 1 \le H, W \le 100
  • 1 \le N \le 16
  • 1 \le C_k \le H \lparen 1 \le k \le N \rparen
  • 1 \le D_k \le W \lparen 1 \le k \le N \rparen
  • (C_k,D_k) 不同 或者
  • 1 \le S_k \le T_k \le 10^9 \lparen 1 \le k \le N \rparen
  • G_{i,j} 满足 # 或 写入 . 任何一个 \lparen 1 \le i \le H, 1 \le j \le W \rparen
  • 方块和有炸弹的方块 \lparen 1,1 \rparen 是路
  • 质量 (1,1) 附近道路上的广场 1 存在多个 通过移动
  • H, W, N, C_k, D_k, S_k, T_k 是整数

入力

输入将以以下形式从标准输入给出。

H\ W\ N
C_1\ D_1\ S_1\ T_1
C_2\ D_2\ S_2\ T_2
\vdots
C_N\ D_N\ S_N\ T_N
G_{1,1}\ \ldots\ G_{1,W}
\vdots
G_{H,1}\ \ldots\ G_{H,W}

出力

答案 请打印除以 1 行输出。 从


入力例 1

3 3 2
1 3 2 5
3 2 3 4
.#.
...
#.#

例如,(1,1),(2,1),(2,2),(3,2),(2,2),(2,3),(1,3) ,时间 炸弹时 3 您可以取消 2 。时间 6 您可以取消 1 我在一个有炸弹的地方。 1 是时间 我去 2 以上 5 仅在以下情况下才能取消。

出力例 1

1

入力例 2

1 2 1
1 2 1000000000 1000000000
..

出力例 2

0