通话不中断的最短路径 - 华为机试真题题解

分值： 200分

题解： Java / Python / C++

题目描述

给定一个MxN的网格，其中每个单元格都填有数字，数字大小表示覆盖信号强度。灰色网格代表空地，橙色网格代表信号覆盖区域，绿色网格代表基站，绿色网格内数字大小表示该基站发射信号的初始强度。

基站信号每向外（上下左右）传播一格，信号强度减1，最小减为0，表示无信号，如下图示。当某个位置可以同时接收到多个基站的信号时，取其中接收信号强度的最大值作为该位置的信号强度。

对于给定网格，请判断是否存在一条路径，使得从左上角移动到右下角过程中信号不中断，只能上下左右移动。假设接收到的信号强度低于门限Th ，信号就会中断。

注意:出发点固定在网格的左上角，终点是网格的右下角。

输入描述

第一行输入信号强度Th。 (1<= Th <= 100)

第二行输入矩阵M、N。 (1<= M <= 100，1<= N <= 100)

第三行输入基站个数K。 (1<= K <= 100)

后续K行输入基站位置及初始信号强度。(前两个值表示基站所在行、列索引，第3个值表示基站初始信号强度)

输出描述

返回信号不中断的最短