四团网站建设,江西网站优化,如何更改wordpress上的默认头像,惠州市网站建设个人华为20230921秋招T3-PCB印刷电路板布线#xff08;留学生专场#xff09;
题目描述与示例
题目描述
在PCB印刷电路板设计中#xff0c;器件之间的连线#xff0c;要避免线路的阻抗值增大#xff0c;而且器件之间还有别的器任和别的干扰源#xff0c;在布线时我们希望受…华为20230921秋招T3-PCB印刷电路板布线留学生专场
题目描述与示例
题目描述
在PCB印刷电路板设计中器件之间的连线要避免线路的阻抗值增大而且器件之间还有别的器任和别的干扰源在布线时我们希望受到的干扰尽量小。
现将电路板简化成一个M × N的矩阵每个位置单元格的值表示其源干扰度。
如果单元格的值为0表示此位置没有干扰源如果单元格的值为非0则表示此位置是干扰源其值为源干扰度。连线经过干扰源或干扰源附近会增加连线的总干扰度。
位置A[x,y]的干扰源的源干扰广为d (d0)则连线的干扰度计算如下
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 dequeDIRECTIONS [(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] 1grid_new[i][j] valq deque()q.append((i, j))# 注意这里退出循环的条件和val相关while val 1:val - 1qSize len(q)for _ in range(qSize):cur_x, cur_y q.popleft()for dx, dy in DIRECTIONS:nxt_x, nxt_y cur_xdx, cur_ydyif 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] valcheck_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_newif 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 gridNewprivate 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;Dequeint[] 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 pathprivate 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 vectorpairint, int DIRECTIONS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// Function to perform BFS and update grid_new
void BFSUpdateGridNew(int val, vectorvectorint gridNew, int i, int j, int m, int n) {vectorvectorint checkList(m, vectorint(n, 0));checkList[i][j] 1;gridNew[i][j] val;dequepairint, 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 vectorvectorint gridNew, int m, int n) {vectorvectorint dp(m, vectorint(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;vectorvectorint grid(m, vectorint(n));for (int i 0; i m; i) {for (int j 0; j n; j) {cin grid[i][j];}}vectorvectorint gridNew(m, vectorint(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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
