-
大厂秋招真题【BFS+DP】华为20230921秋招T3-PCB印刷电路板布线（留学生专场）
华为20230921秋招T3-PCB印刷电路板布线（留学生专场）
题目描述与示例
题目描述
在PCB印刷电路板设计中，器件之间的连线，要避免线路的阻抗值增大，而且器件之间还有别的器任和别的干扰源，在布线时我们希望受到的干扰尽量小。
现将电路板简化成一个
M × N的矩阵，每个位置（单元格）的值表示其源干扰度。如果单元格的值为
0，表示此位置没有干扰源，如果单元格的值为非0，则表示此位置是干扰源，其值为源干扰度。连线经过干扰源或干扰源附近会增加连线的总干扰度。位置
A[x,y]的干扰源的源干扰广为d (d>0)，则连线的干扰度计算如下：1、若连线经过位置
A[x,y]，则其总干扰度会增加加2、若连线经过离位置
A[x,y]距离小于d的位置时，设其距离为k，则总干扰度会增加(d-k)3、若连线经过离位置
A[x,y]距离大于或等于d的位置时，总干扰都不会增加；注：位置
[x1,y1]和位置[x2,y2]之间距离的定义为：|x1-x2|+|y1-y2|。如下
3x3矩阵，位置[1,1]的源干扰度是2，连线的位置序列为：[0,0]->[0,1]->[0,2]->[1,2]->[2,2]。
其中
[0,1]和[1,0]到干扰源的距离为1，会叠加1的干扰度；其他位置到[1,1]的距离均大于等于2，所以不会叠加干扰度。因此这条连线的总干扰度为2。现在我们需要将左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的
[0,0]和右下角的[M-1,N-1]。由于我们希望连线尽量地短，从位置[0,0]到[M-1,N-1]的连线途中，我们规定连线只能向下或向右。请根据输入(
M × N的矩阵)，计算出连线的最小干扰度。输入描述
第一行是两个整数
M和N(M和N最大值为1000)，表示行数和列数；接着是
M行的数据，每一包含N个整数，代表每个位置的源干扰度，每个源干扰度小于50。输出描述
左上角
[0,0]到右下角[M-1,N-1]连线的最小总干扰度。示例一
输入
3 3 0 0 0 0 2 0 0 0 0- 1
- 2
- 3
- 4
输出
2- 1
说明
其中一条可以使干扰度最小的路径为：
[0,0]->[0,1]->[0,2]->[1,2]->[2,2]，其干扰度为2。示例二
输入
5 5 0 0 0 0 0 0 0 2 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0- 1
- 2
- 3
- 4
- 5
- 6
输出
1- 1
说明
先从
[0,0]往下走到最下面[4,0]，再往石走到右下角[4,4]，途径[2,0]时叠加一个干扰度。示例三
输入
5 5 0 0 0 0 0 0 0 2 0 0 0 2 0 2 0 0 0 2 0 0 0 0 0 0 0- 1
- 2
- 3
- 4
- 5
- 6
输出
2- 1
时空限制
时间限制： C/C++
2000MS，其他语言4000MS内存限制： C/C++
256MB，其他语言512MB解题思路
本题属于综合性较强的题目，结合了BFS和DP两个知识点。
首先我们需要根据原矩阵，构建出每一个位置干扰值叠加的结果，得到一个新的矩阵
grid_new。这里显然就是一个基于BFS计算层数的问题。
在得到新的矩阵
grid_new之后，问题就转变为，对grid_new构建一条从左上到右下的路径，每次只能够向右或向下移动，路径经过的点的总和需要最小。这是一个经典的路径DP问题，和LeetCode64、最小路径和完全一致。代码
Python
# 题目：【DP】华为2023秋招-PCB印刷电路板布线 # 作者：闭着眼睛学数理化 # 算法：DP/BFS # 代码有看不懂的地方请直接在群上提问 from collections import deque DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 对于grid中每一个干扰源，以干扰源作为起点进行BFS，更新grid_new def BFS_update_grid_new(val, grid_new, i, j, m, n): check_list = [[0] * n for _ in range(m)] check_list[i][j] = 1 grid_new[i][j] += val q = deque() q.append((i, j)) # 注意这里退出循环的条件和val相关 while val > 1: val -= 1 qSize = len(q) for _ in range(qSize): cur_x, cur_y = q.popleft() for dx, dy in DIRECTIONS: nxt_x, nxt_y = cur_x+dx, cur_y+dy if 0 <= nxt_x < m and 0 <= nxt_y < n and check_list[nxt_x][nxt_y] == 0: q.append((nxt_x, nxt_y)) grid_new[nxt_x][nxt_y] += val check_list[nxt_x][nxt_y] = 1 # 用于解决最小路径和问题的函数 def find_min_sum_path(grid_new, m, n): # 构建大小为m*n的dp数组，dp[i][j]表示 # 到达grid_new中的点(i,j)，所需的最小路径和 dp = [[0] * (n) for _ in range(m)] # 初始化(0,0)位置 dp[0][0] = grid_new[0][0] # 初始化dp数组第0行，只能从左边向右转移得到 for j in range(1, n): dp[0][j] += dp[0][j-1] + grid_new[0][j] # 初始化dp数组第0列，只能从上边向下转移得到 for i in range(1, m): dp[i][0] += dp[i-1][0] + grid_new[i][0] # 遍历剩余所有点 # 点(i,j)的状态，只能从点(i-1,j)向下或者从点(i,j-1)向右转移得到 # 故动态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid_new[i][j] for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid_new[i][j] return dp[-1][-1] # 输入行数m，列数n m, n = map(int, input().split()) # 构建原干扰值矩阵 grid = list() for _ in range(m): grid.append(list(map(int, input().split()))) # 初始化干扰值叠加后的新矩阵gird_new grid_new = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): # 对于每一个干扰源，使用BFS更新grid_new if grid[i][j] != 0: val = grid[i][j] BFS_update_grid_new(val, grid_new, i, j, m, n) # 调用函数find_min_sum_path，输出答案 print(find_min_sum_path(grid_new, m, n))- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
Java
import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Main { private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Function to perform BFS and update gridNew private static void BFSUpdateGridNew(int val, int[][] gridNew, int i, int j, int m, int n) { int[][] checkList = new int[m][n]; checkList[i][j] = 1; gridNew[i][j] += val; Deque<int[]> queue = new ArrayDeque<>(); queue.add(new int[]{i, j}); while (val > 1) { val--; int qSize = queue.size(); for (int k = 0; k < qSize; k++) { int[] current = queue.poll(); int curX = current[0]; int curY = current[1]; for (int[] dir : DIRECTIONS) { int nextX = curX + dir[0]; int nextY = curY + dir[1]; if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && checkList[nextX][nextY] == 0) { queue.add(new int[]{nextX, nextY}); gridNew[nextX][nextY] += val; checkList[nextX][nextY] = 1; } } } } } // Function to find the minimum sum path private static int findMinSumPath(int[][] gridNew, int m, int n) { int[][] dp = new int[m][n]; dp[0][0] = gridNew[0][0]; for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + gridNew[i][0]; } for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + gridNew[0][j]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + gridNew[i][j]; } } return dp[m - 1][n - 1]; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] grid = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { grid[i][j] = sc.nextInt(); } } int[][] gridNew = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] != 0) { int val = grid[i][j]; BFSUpdateGridNew(val, gridNew, i, j, m, n); } } } System.out.println(findMinSumPath(gridNew, m, n)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
C++
#include#include #include using namespace std; const vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Function to perform BFS and update grid_new void BFSUpdateGridNew(int val, vector<vector<int>>& gridNew, int i, int j, int m, int n) { vector<vector<int>> checkList(m, vector<int>(n, 0)); checkList[i][j] = 1; gridNew[i][j] += val; deque<pair<int, int>> q; q.push_back({i, j}); while (val > 1) { val--; int qSize = q.size(); for (int k = 0; k < qSize; k++) { int curX = q.front().first; int curY = q.front().second; q.pop_front(); for (const auto& dir : DIRECTIONS) { int nextX = curX + dir.first; int nextY = curY + dir.second; if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && checkList[nextX][nextY] == 0) { q.push_back({nextX, nextY}); gridNew[nextX][nextY] += val; checkList[nextX][nextY] = 1; } } } } } // Function to find the minimum sum path int FindMinSumPath(const vector<vector<int>>& gridNew, int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); dp[0][0] = gridNew[0][0]; for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + gridNew[i][0]; } for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + gridNew[0][j]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + gridNew[i][j]; } } return dp[m - 1][n - 1]; } int main() { int m, n; cin >> m >> n; vector<vector<int>> grid(m, vector<int>(n)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; } } vector<vector<int>> gridNew(m, vector<int>(n, 0)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] != 0) { int val = grid[i][j]; BFSUpdateGridNew(val, gridNew, i, j, m, n); } } } cout << FindMinSumPath(gridNew, m, n) << endl; return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
时空复杂度
时间复杂度：
O(MNk)。其中k为干扰源的数目，一共需要进行k次BFS，每次BFS的时间复杂度为O(MN)。另外，DP过程的时间复杂度为O(MN)。空间复杂度：
O(MN)。grid_new、check_list、dp等二维矩阵所占空间均为O(MN)。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
-
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
-
绿色聊天软件戳
od1336了解更多
-
相关阅读:
docker搭建Redis三主三从
部分SOP-8双运放选型参考
互联网轻量级框架整合之JavaEE基础II
计算机网络-----IP地址分配
基本数据结构与算法JavaAPI【1】--线性表篇
【独立全开源】点大商城V2-2.5.2 新增 微信小程序隐私协议弹窗
谈谈ORACLE应用数据同步器：Primavera Gateway
原型和原型链
python os.system( 没有那个文件或目录
ResNet简单解释
- 原文地址：https://blog.csdn.net/weixin_48157259/article/details/133435463
