通话不中断的最短路径 - 华为机试真题题解
分值： 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找到从左上角到右下角的最短路径。
- 使用DFS在网格上模拟基站信号辐射过程，记录每个格子上的信号强度。
- 使用BFS搜索从左上角到右下角的最短路径，考虑信号强度和信号门限。
代码大致描述
- 输入Th，M，N，K，以及每个基站的位置和初始信号强度。
- 使用DFS模拟基站信号辐射，记录每个格子的信号强度。
- 使用BFS搜索从左上角到右下角的最短路径，考虑信号强度和信号门限。
- 输出最短路径的长度。
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) continue;
vis[nr][nc] = true;
q.offer(new int[]{nr, nc});
}
}
step++;
}
System.out.println(0);
}
// 模拟基站信号向外辐射
public static void dfs(int[][] g, int r, int c, int x, boolean[][] vis) {
// 网格外，已访问，信号量过低
if (r < 0 || c < 0 || r >= M || c >= N || vis[r][c] || x < Th) return;
g[r][c] = Math.max(g[r][c], x);
vis[r][c] = true;
int[] dirs = new int[]{-1, 0, 1, 0, -1};
for (int i = 1; i < 5; i++) {
int nr = r + dirs[i - 1], nc = c + dirs[i];
dfs(g, nr, nc, x - 1, vis);
}
}
}
Python
from collections import deque
def dfs(g, r, c, x, vis):
if r < 0 or c < 0 or r >= M or c >= N or vis[r][c] or x < Th or x <= g[r][c]:
return
g[r][c], vis[r][c] = x, True
dirs = [-1, 0, 1, 0, -1]
for i in range(1, 5):
nr, nc = r + dirs[i - 1], c + dirs[i]
dfs(g, nr, nc, x - 1, vis)
def main():
global M, N, Th
Th = int(input())
M, N = map(int, input().split())
K = int(input())
g = [[0] * N for _ in range(M)]
for _ in range(K):
r, c, x = map(int, input().split())
dfs(g, r, c, x, [[False] * N for _ in range(M)])
vis = [[False] * N for _ in range(M)]
q = deque()
if g[0][0] != 0:
q.append((0, 0))
vis[0][0] = True
step = 0
while q:
size = len(q)
for _ in range(size):
r, c = q.popleft()
if r == M - 1 and c == N - 1:
print(step)
return
dirs = [-1, 0, 1, 0, -1]
for i in range(1, 5):
nr, nc = r + dirs[i - 1], c + dirs[i]
if 0 <= nr < M and 0 <= nc < N and not vis[nr][nc] and g[nr][nc]:
vis[nr][nc] = True
q.append((nr, nc))
step += 1
print(0)
if __name__ == "__main__":
main()
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int M, N, Th;
// 模拟基站信号向外辐射
void dfs(vector<vector<int>>& g, int r, int c, int x, vector<vector<bool>>& vis) {
// 网格外，已访问，信号量过低
if (r < 0 || c < 0 || r >= M || c >= N || vis[r][c] || x < Th || g[r][c] >= x) return;
g[r][c] = x;
vis[r][c] = true;
int dirs[] = {-1, 0, 1, 0, -1};
for (int i = 1; i < 5; i++) {
int nr = r + dirs[i - 1], nc = c + dirs[i];
dfs(g, nr, nc, x - 1, vis);
}
}
int main() {
cin >> Th >> M >> N;
int K;
cin >> K;
vector<vector<int>> g(M, vector<int>(N, 0));
for (int i = 0; i < K; i++) {
int r, c, x;
cin >> r >> c >> x;
vector<vector<bool>> vis(M, vector<bool>(N, false));
dfs(g, r, c, x, vis);
}
vector<vector<bool>> vis(M, vector<bool>(N, false));
queue<pair<int, int>> q;
if (g[0][0] != 0) {
q.push({0, 0});
vis[0][0] = true;
}
int step = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
pair<int, int> p = q.front();
q.pop();
int r = p.first, c = p.second;
if (r == M - 1 && c == N - 1) {
cout << step << endl;
return 0;
}
int dirs[] = {-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) continue;
vis[nr][nc] = true;
q.push({nr, nc});
}
}
step++;
}
cout << 0 << endl;
return 0;
}
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。
#校招##秋招##面经##华为##笔试#
类似资料：