配点 : 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