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

分值： 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个值表示基站初始信号强度)

输出描述

返回信号不中断的最短路径，不存在返回0

示例1

输入：
1
4 4
2
0 1 2
3 2 3

输出：
6

解释: 
1) 信号强度门限Th = 1
2) M=4，N=4
3) 4*4网格中一共包含2个基站
4) 2个基站的位置，其中第1个基站在第0行第1列、初始信号强度 =2;第2个基站在第3行第2列、初始信号强度=3

注:如上Grid，绿色表示基站，橙色为基站信号往外传播后覆盖的区域;按照图中箭头方向移动路径最短，为6

示例2

输入：
1
3 3
2
0 1 2
1 1 2

输出：
0

解释：
1) 信号强度门限Th = 1
2) M=3，N=3
3) 3*3网格中一共包含2个基站
4) 2个基站的位置，其中第1个基站在第0行第1列、初始信号强度 = 2;第2个基站在第1行第1列、初始信号强度 =2;

注:如上Grid，绿色表示基站，橙色为基站信号往外传播后覆盖的区域;如图，第2行第2列无信号覆盖，返回0

题解

解题思路

题目可以通过深度优先搜索（DFS）和广度优先搜索（BFS）结合来解决。首先，通过DFS模拟基站信号的辐射过程，然后使用BFS找到从左上角到右下角的最短路径。

1. 使用DFS在网格上模拟基站信号辐射过程，记录每个格子上的信号强度。
2. 使用BFS搜索从左上角到右下角的最短路径，考虑信号强度和信号门限。

代码大致描述

1. 输入Th，M，N，K，以及每个基站的位置和初始信号强度。
2. 使用DFS模拟基站信号辐射，记录每个格子的信号强度。
3. 使用BFS搜索从左上角到右下角的最短路径，考虑信号强度和信号门限。
4. 输出最短路径的长度。

Java

package contest.acmcoder.p1;


import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    static int M, N, Th;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Th = in.nextInt();
        M = in.nextInt();
        N = in.nextInt();
        int K = in.nextInt();
        int[][] g = new int[M][N];
        for (int i = 0; i < K; i++) {
            int r = in.nextInt(), c = in.nextInt(), x = in.nextInt();
            dfs(g, r, c, x, new boolean[M][N]);
        }

        boolean[][] vis = new boolean[M][N];
        Queue<int[]> q = new ArrayDeque<>();
        if (g[0][0] != 0) {
            q.offer(new int[]{0, 0});
            vis[0][0] = true;
        }
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] p = q.poll();
                int r = p[0], c = p[1];

                if (r == M - 1 && c == N - 1) {
                    System.out.println(step);
                    return;
                }

                int[] dirs = new int[]{-1, 0, 1, 0, -1};
                for (int j = 1; j < 5; j++) {
                    int nr = r + dirs[j - 1], nc = c + dirs[j];

                    if (nr < 0 || nc < 0 || nr >= M || nc >= N || vis[nr][nc] || g[nr][nc] == 0) cont