大厂秋招真题【BFS+DP】华为20230921秋招T3-PCB印刷电路板布线(留学生专场)

这篇具有很好参考价值的文章主要介绍了大厂秋招真题【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]

大厂秋招真题【BFS+DP】华为20230921秋招T3-PCB印刷电路板布线(留学生专场),大厂秋招真题,# dp,华为,华为,算法,数学建模,leetcode,宽度优先,动态规划

其中[0,1][1,0]到干扰源的距离为1,会叠加1的干扰度;其他位置到[1,1]的距离均大于等于2,所以不会叠加干扰度。因此这条连线的总干扰度为2

现在我们需要将左上角的器件到右下角的器件进行连线,两个器件的位置分别是左上角的[0,0]和右下角的[M-1,N-1]。由于我们希望连线尽量地短,从位置[0,0][M-1,N-1]的连线途中,我们规定连线只能向下或向右。

请根据输入(M × N的矩阵),计算出连线的最小干扰度。

输入描述

第一行是两个整数MN(MN最大值为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计算层数的问题。

大厂秋招真题【BFS+DP】华为20230921秋招T3-PCB印刷电路板布线(留学生专场),大厂秋招真题,# dp,华为,华为,算法,数学建模,leetcode,宽度优先,动态规划

在得到新的矩阵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_newcheck_listdp等二维矩阵所占空间均为O(MN)


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多文章来源地址https://www.toymoban.com/news/detail-727380.html

到了这里,关于大厂秋招真题【BFS+DP】华为20230921秋招T3-PCB印刷电路板布线(留学生专场)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023小米秋招真题-手机流畅运行的秘密

    这是一道小米面试题,使用 贪心的思想 。 8月份发布会一结束,米小兔就在公司领到了一台最新发布的XiaomiMX Fold3手机。这是一款小米舰折屏手机,并搭载了全新升级架构的MIU114系统。其先进的应用引擎不仅让系统更流畅,应用体验也大幅提升。在一个优化项中,为了尽可能

    2024年02月09日
    浏览(36)
  • Educational Codeforces Round 153 D-E dp,bfs

    1860D Balanced String 首先只能是0和1交换,1在 i i i 位置,0在 j j j 位置,每交换一次产生的贡献是 2 ∗ ( i − j ) 2*(i-j) 2 ∗ ( i − j ) ,所以我们可以先算出原01串中所需要的贡献 m m m ,我们发现找到 t o l tol t o l 个1和0的位置 i k , j k i_k,j_k i k ​ , j k ​ 且 ∑ k t o l i k − j k = m

    2024年02月12日
    浏览(42)
  • 算法沉淀——多源 BFS(leetcode真题剖析)

    多源 BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的 BFS 中,我们通常从一个起始点开始,逐层遍历所有的相邻节点。而在多源 BFS 中,我们可以同时从多个源点开始,从这些源点出发,逐层向外扩展,直到达到目标或者遍历完整个图。 多源 BFS 可以用于解决一些

    2024年02月19日
    浏览(43)
  • 大厂sql真题讲解(黑马)

    http://yun.itheima.com/open/853.html | 面试宝典-如何备战大厂SQL真题 http://yun.itheima.com/open/858.html | 面试宝典–大厂必考知识开窗函数 http://yun.itheima.com/open/864.html | 面试宝典-详解美团SQL真题 http://yun.itheima.com/open/868.html | 图解大厂SQL-腾讯面试真题详解(四) http://yun.itheima.com/open/870.

    2024年02月17日
    浏览(30)
  • 算法沉淀——BFS 解决拓扑排序(leetcode真题剖析)

    Breadth-First Search (BFS) 在拓扑排序中的应用主要是用来解决有向无环图(DAG)的拓扑排序问题。拓扑排序是对有向图中所有节点的一种线性排序,使得对于每一条有向边 (u, v),节点 u 在排序中都出现在节点 v 的前面。如果图中存在环路,则无法进行拓扑排序。 BFS 解决拓扑排序

    2024年02月21日
    浏览(39)
  • 算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

    BFS(广度优先搜索)解决 Flood Fill 算法的基本思想是通过从起始点开始,逐层向外扩展,访问所有与起始点相连且具有相同特性(颜色等)的区域。在 Flood Fill 中,通常是通过修改图像的像素颜色。 下面是 BFS 解决 Flood Fill 算法的步骤: 初始化: 将起始点的颜色修改为新的

    2024年02月20日
    浏览(37)
  • 算法沉淀——BFS 解决最短路问题(leetcode真题剖析)

    BFS (广度优先搜索)是解决最短路径问题的一种常见算法。在这种情况下,我们通常使用BFS来查找从一个起始点到目标点的最短路径。 具体步骤如下: 初始化: 从起始点开始,将其放入队列中,并标记为已访问。 BFS遍历: 不断从队列中取出顶点,然后探索与该顶点相邻且

    2024年02月20日
    浏览(38)
  • 【精选】护网面试题4.0 (大厂真题)

    目录 1.设备误报如何处理? 2.如何区分扫描流量和手工流量? 3.网站被上传webshell如何处理? 4.给你一个比较大的日志,应该如何分析? 5.了解安全设备嘛? 6.了解过系统加固吗? 7.CS是什么东西,知道怎么使用吗? 8.WAF方面有没有了解过,清楚WAF的分类和原理吗? 9.Powershe

    2024年01月17日
    浏览(37)
  • 2022大厂高频软件测试面试真题(附答案)

    接口测试实际跟一般测试不同就是测试用例的设计部分。 获取接口规范。 设计接口测试功能用例(主要从用户角度出发看接口能否实现业务需求,用例设计就是黑盒用例那一套)。 各种入参验证(正常情况,异常情况包括输入参数个数不对,类型不对,可选/必选,还有考虑

    2023年04月08日
    浏览(52)
  • 一线大厂面试真题-Kafka如何保证消息不丢失

    目录 问题解答 面试点评 (如图) kafka 是 一个用来实现异步消息通信的中间件,它的整个架构由Producer、 Consumer 、 Broker组成。 所以,对于 kafka 如 何保证消息不丢失这个问题,可以从三个方面来考虑和实现 : 首先 是Producer端,需要确保消息能够到达Broker并实现消息存储,在这

    2024年02月01日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包