现有一个 n 行 m 列的网格迷宫，每个方格要么是可以通过的空方格，要么是不可通过的墙方格，迷宫的四周边界外都是墙方格。初始时，迷宫中不存在墙方格。 我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的方格，里面有 a_i,j 个金币。 在开始移动前，小K已经知道了 t 条信息，每条信息以一个三元组 x, y, v 表示，代表 (x,y) 方格会在第 v 回合永久变成墙方格（在此之前金币仍可收集）。每一回合开始时，方格先发生变化，小K再进行移动（特别地，如果起点在第一回合变为墙方格，视作小K不受影响）。 小K从左上角 (1,1) 方格出发，记当前所在的位置为 (x,y) ，每回合只能向右移动一格到达 (x,y+1) 或向下移动一格到达 (x+1,y) 。每一个方格中的金币只能收集一次，请问小K最多能收集到多少金币？
第一行输入两个整数 n,m(1≤ n,m ≤ 1000) 代表迷宫的大小。 此后 n 行，每行输入 m 个整数 a_i,1,a_i,2,...,a_i,m (1≤ a_i,j ≤ 100) 代表每个迷宫方格的金币数量。 第 n+2 行输入一个整数 t (1≤ t≤ n× m) 代表信息条数。 此后 t 行，每行输入三个整数 x,y,v (1≤ x ≤ n;1≤ y ≤ m;1≤ v ≤ n × m) 代表一条信息。保证每一条信息的 (x,y) 互不相同。
输出一个整数，代表小K最多能收集到的金币数量。
3 3 1 100 100 1 100 100 1 1 1 3 1 1 1 1 2 1 2 2 2
5
3 3 1 100 100 100 100 100 100 100 100 2 2 1 1 1 2 1
1
考点：广度优先搜索(BFS)
数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
参考方向：广度优先搜索(BFS)
按层扩散搜索，无权图上第一次到达即最短路。
思路框架（广度优先搜索(BFS) 通法 · 非本题专属）
实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。
复杂度：时间 O(V+E) ｜ 空间 O(V)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例 1：输入 3 3 / 1 100 100 / 1 100 100 / 1 1 1 / 3 / 1 1 1 / 1 2 1 / 2 2 2 → 输出 5
在这个样例中，我们使用 表示墙方格，用 表示小K当前回合所在的位置。初始时，迷宫状态如公式所示： bmatrix & 100 & 100 \ 1 & 100 & 100 \ 1 & 1 & 1 bmatrix bullet & 100 & 100 \
1 & 100 & 100 \
1 & 1 & 1
end{bmatrix}" />。
第一回合：由于 (1,2) 会在第一回合变为墙方格，所以他只能走到 (2,1) ，第一回合结束时，小K已经得到了 2 个金币，迷宫状态如公式所示： bmatrix & & 100 \ & 100 & 100 \ 1 & 1 & 1 bmatrix Box & Box & 100 \
bullet & 100 & 100 \
1 & 1 & 1
end{bmatrix}" />。
第二回合，小K只能向下移动到 (2,2) ，第二回合结束时，小K已经得到了 3
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：华为机试编程模拟题5。