题目描述

在游戏世界中，给定一个 $M$ * $N$ 的网格，其中每个单元格都填有数字，数字大小表示覆盖能量强度。灰色网格代表禁地，橙色网格代表能量覆盖区域，绿色网格代表生命之树，绿色网格内数字大小表示该生命之树散发的能量的初始强度。 已知每个网格内的能量强度每向外(上下左右)传播一格，能量强度减 $1$，最小减为 $0$ 。

表示无信号，如下图示。当某个位置可以同时接收到多棵生命之树的能量时，取其中接收能量强度的最大值作为该位置的能量强度，对于给定网格，请判断是否存在一条路径，使得从左上角移动到右下角过程中能量不中断，只能上下左右移动。假设接吸收的能量强度低于门限 $Th$ ，能量就会中断。

题面描述

在一个 $M \times N$ 的网格中，每个单元格代表不同的能量强度，其中灰色单元格为禁地，橙色单元格为能量覆盖区域，绿色单元格为生命之树，表示生命之树散发的初始能量强度。能量强度会向外传播，每向外一格减少 $1$，最低为 $0$。若某位置接收到多棵生命之树的能量，取最大值。如果能量强度低于阈值 $Th$，则能量中断。任务是从左上角到右下角寻找一条信号不中断的最短路径，若不存在则返回 $0$。

思路：Dijkstra算法，最短路

容易这个问题可以分成两部分求解： 第一步：求解网格内每个点的最大信号强度。 第二步：对最大信号强度大于等于 $Th$，且相邻的点对连边，最后输出出发点到终点的最短路。