C - Time Bombs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 にあります。

kentand君は時刻 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