收集金币__牛客网

$\hspace{15pt}$ 现有一个 $n$ 行 $m$ 列的网格迷宫，每个方格要么是可以通过的空方格，要么是不可通过的墙方格，迷宫的四周边界外都是墙方格。初始时，迷宫中不存在墙方格。
$\hspace{15pt}$ 我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的方格，里面有 $a_{i,j}$ 个金币。
$\hspace{15pt}$ 在开始移动前，小K已经知道了 $t$ 条信息，每条信息以一个三元组 $\{x, y, v\}$ 表示，代表 $(x,y)$ 方格会在第 $v$ 回合永久变成墙方格（在此之前金币仍可收集）。每一回合开始时，方格先发生变化，小K再进行移动（特别地，如果起点在第一回合变为墙方格，视作小K不受影响）。
$\hspace{15pt}$ 小K从左上角 $(1,1)$ 方格出发，记当前所在的位置为 $(x,y)$ ，每回合只能向右移动一格到达 $(x,y+1)$ 或向下移动一格到达 $(x+1,y)$ 。每一个方格中的金币只能收集一次，请问小K最多能收集到多少金币？

$\hspace{15pt}$ 第一行输入两个整数 $n,m\left(1\leqq n,m \leqq 1000\right)$ 代表迷宫的大小。
$\hspace{15pt}$ 此后 $n$ 行，每行输入 $m$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,m} \left(1\leqq a_{i,j} \leqq 100\right)$ 代表每个迷宫方格的金币数量。
$\hspace{15pt}$ 第 $n+2$ 行输入一个整数 $t \left(1\leqq t\leqq n\times m\right)$ 代表信息条数。
$\hspace{15pt}$ 此后 $t$ 行，每行输入三个整数 $x,y,v \left(1\leqq x \leqq n;\ 1\leqq y \leqq m;\ 1\leqq v \leqq n \times m\right)$ 代表一条信息。保证每一条信息的 $(x,y)$ 互不相同。

说明

在这个样例中，我们使用  表示墙方格，用  表示小K当前回合所在的位置。初始时，迷宫状态如公式所示：。

第一回合：由于  会在第一回合变为墙方格，所以他只能走到 ，第一回合结束时，小K已经得到了  个金币，迷宫状态如公式所示：。

第二回合，小K只能向下移动到 ，第二回合结束时，小K已经得到了  个金币，迷宫状态如公式所示：。

剩余的回合，迷宫不再发生变化，而由于小K只能向下或者右移动，所以他至多收集到  和  两个方格的金币。加起来刚好是  个金币。

收集金币

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题