题面描述
在一个 M×N 的网格中，每个单元格代表不同的能量强度，其中灰色单元格为禁地，橙色单元格为能量覆盖区域，绿色单元格为生命之树，表示生命之树散发的初始能量强度。能量强度会向外传播，每向外一格减少 1，最低为 0。若某位置接收到多棵生命之树的能量，取最大值。如果能量强度低于阈值 Th，则能量中断。任务是从左上角到右下角寻找一条信号不中断的最短路径，若不存在则返回 0。
思路：Dijkstra算法，最短路
容易这个问题可以分成两部分求解：
第一步：求解网格内每个点的最大信号强度。
第二步：对最大信号强度大于等于 Th，且相邻的点对连边，最后输出出发点到终点的最短路。
题目描述
在游戏世界中，给定一个 M * N 的网格，其中每个单元格都填有数字，数字大小表示覆盖能量强度。灰色网格代表禁地，橙色网格代表能量覆盖区域，绿色网格代表生命之树，绿色网格内数字大小表示该生命之树散发的能量的初始强度。
已知每个网格内的能量强度每向外(上下左右)传播一格，能量强度减 1，最小减为 0 。
表示无信号，如下图示。当某个位置可以同时接收到多棵生命之树的能量时，取其中接收能量强度的最大值作为该位置的能量强度，对于给定网格，请判断是否存在一条路径，使得从左上角移动到右下角过程中能量不中断，只能上下左右移动。假设接吸收的能量强度低于门限 Th ，能量就会中断。
注意:出发点固定在网格的左上角，终点是网格的右下角。
输入
第一行输入能量强度 Th 。( 1≤Th≤100)
第二行输入矩阵 M 、N 。(1≤M≤100，1≤N≤100)
第三行输入生命之树的个数 K。 (1≤K≤100)
后续 K 行输入生命之树的位置及初始能量强度。(前两个值表示生命之树所在行、列索引，第 3 个值表示生命之树初始能量强度)
输出
返回信号不中断的最短路径，不存在返回 0。
样例1
输入
1
4 4
2
0 1 2
3 2 3
输出
6
说明
-
能量强度门限 Th = 1
-
M = 4,N = 4
-
4 * 4 网格中一共包含 2 棵生命之树
-
2 棵生命之树的位置，其中第 1 个生命之树在第 0 行第 1 列、初始能量强度 = 2 ；第 2 棵生命之树在第 3 行第 2 列、初始能量强度 = 3
image.png
样例2
输入
1
5 5
5
0 1 2
0 4 3
2 3 2
4 0 3
4 3 2
输出
8
说明
- 能量强度门限 Th = 1
- M = 5 , N = 5
- 5 * 5 网格中一共包含 5 棵生命之树
- 5 棵生命之树的位置，其中第 1 棵生命之树在第 0 行第 1 列、初始能量强度 = 2:第 2 棵生命之树在第 0 行第 4列、初始能量强度 =3;第 3 棵生命之树在第 2 行第 3 列、初始能量强度 = 2 ;第 4 棵生命之树在第 4 行第 0 列 、初始能量强度 3 ;第 5 棵生命之树在第 4 行第 3 列、初始能量强度= 2;
image.png
注：如上Grid ，绿色表示生命之树，橙色为生命之树散发的能量往外传播后覆盖的区域，按照途中箭头方向移动路径最短。
