华为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
输出
2
说明
其中一条可以使干扰度最小的路径为:[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
说明
先从[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
输出
2
时空限制
时间限制: 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))
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));
}
}
C++
#include <iostream>
#include <vector>
#include <deque>
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;
}
时空复杂度
时间复杂度: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真题汇总(持续更新)文章来源:https://www.toymoban.com/news/detail-727380.html
-
绿色聊天软件戳
od1336
了解更多文章来源地址https://www.toymoban.com/news/detail-727380.html
到了这里,关于大厂秋招真题【BFS+DP】华为20230921秋招T3-PCB印刷电路板布线(留学生专场)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!