当前位置：首页 > news >正文

机试题——PCB印刷电路板布线

news 来源：原创 2025/5/9 10:11:47

题目描述

在 PCB 印刷电路板设计中，器件之间的连线需要避免线路的阻抗值增大，而且器件之间还可能存在其他干扰源。为了简化问题，我们将电路板简化为一个 ( M * N ) 的矩阵，每个位置（单元格）的值表示其源干扰度。

如果单元格的值为 0，表示此位置没有干扰源。
如果单元格的值为非 0，则表示此位置是干扰源，其值为源干扰度。

连线经过干扰源或干扰源附近会增加连线的总干扰度，具体规则如下：

若连线经过位置 ( A[x,y] )，其源干扰度为 ( d )，则总干扰度增加 ( d )。
若连线经过离位置 ( A[x,y] ) 距离小于 ( d ) 的位置，设其距离为 ( K )，则总干扰度增加 ( d - K )。
若连线经过离位置 ( A[x,y] ) 距离大于或等于 ( d ) 的位置，则总干扰度不会增加。

位置 ( [x_1,y_1] ) 和位置 ( [x_2,y_2] ) 之间的距离定义为：

|x_1 - x_2| + |y_1 - y_2|

现在需要从左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的 ( [0,0] ) 和右下角的 ( [M-1,N-1] )。连线只能向下或向右。

输入描述

第一行包含两个整数 ( M ) 和 ( N )（( M ) 和 ( N ) 的最大值为 1000），表示行数和列数。

接下来是 ( M ) 行数据，每行包含 ( N ) 个整数，代表每个位置的源干扰度，每个源干扰度小于 50。

输出描述

输出左上角 ( [0,0] ) 到右下角 ( [M-1,N-1] ) 连线的最小总干扰度。

用例输入

输入：

输出：

说明：
其中一条可以使干扰度最小的路径为：

[0,0] [0,1] [0,2] [1,2] [2,2]

其干扰度为 2。

解题思路

问题分析

目标：计算从左上角到右下角的最小干扰度路径。
关键点：
- 每个单元格的干扰度取决于其源干扰度以及周围单元格的距离。
- 干扰度的计算需要考虑源干扰度和距离的关系。
- 路径只能向下或向右。

算法设计

数据结构：
- 使用二维数组 nums 存储每个单元格的源干扰度。
- 使用二维数组 g 存储每个单元格的实际干扰度。
- 使用二维数组 dp 存储从起点到每个单元格的最小干扰度。
计算每个单元格的干扰度：
- 遍历所有单元格，对于每个干扰源，计算其对周围单元格的干扰度。
- 使用曼哈顿距离公式计算距离，并根据规则更新每个单元格的干扰度。
动态规划：
- 初始化 dp[0][0] 为起点的干扰度。
- 遍历每个单元格，更新 dp 数组：
  - 如果在第一行，只能从左边来。
  - 如果在第一列，只能从上面来。
  - 其他位置可以从左边或上面来，选择干扰度较小的路径。
结果计算：
- dp[M-1][N-1] 即为从左上角到右下角的最小干扰度。

代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;int nums[1005][1005];
int g[1005][1005];
int dp[1005][1005];// 计算曼哈顿距离
int get_d(int x1, int y1, int x2, int y2) {return abs(x1 - x2) + abs(y1 - y2);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m; // 输入行数和列数vector<vector<int>> f; // 存储所有干扰源的位置和干扰度f.reserve(1000000);// 读取每个单元格的源干扰度for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> nums[i][j];if (nums[i][j]) {f.push_back({i, j, nums[i][j]});}g[i][j] = 0;dp[i][j] = INT_MAX / 2;}}// 计算每个单元格的干扰度for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int k = 0; k < f.size(); k++) {int d = get_d(i, j, f[k][0], f[k][1]);if (d > f[k][2]) continue;g[i][j] += (f[k][2] - d);}}}// 初始化起点的干扰度dp[0][0] = g[0][0];// 动态规划计算最小干扰度for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i == 0 && j == 0) continue;if (i == 0) dp[i][j] = dp[i][j - 1] + g[i][j];else if (j == 0) dp[i][j] = dp[i - 1][j] + g[i][j];else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + g[i][j];}}// 输出结果cout << dp[n - 1][m - 1] << endl;return 0;
}

机试题——PCB印刷电路板布线

题目描述在 PCB 印刷电路板设计中，器件之间的连线需要避免线路的阻抗值增大，而且器件之间还可能存在其他干扰源。为了简化问题，我们将电路板简化为一个 ( M * N ) 的矩阵，每个位置（单元格）的值表示其源干…...

编程日记 2025/5/9 10:11:47

数据化管理（一）---什么是数据化管理

目录一、什么是数据化管理1.1 “聪明”的销售人员1.2 数据化管理的概念1.3 数据化管理的意义1.4 数据化管理的四个层次1.4.1 业务指导管理1.4.2 营运指导管理1.4.3 经营策略管理1.4.4 战略规划管理 1.5 数据化管理流程图1.5.1 分析需求1.5.2 收集数据1.5.3 整理数据1.5.4 分析…...

编程日记 2025/5/9 10:09:10

Android 10.0 通过广播控制systemui状态栏动态显示和隐藏功能实现

1.前言在10.0的系统rom定制化开发中，在某些特定的产品开发中，需要通过接口来控制系统状态栏的显示和隐藏， 所以就需要了解systemui状态栏的显示构造过程，然后通过相关接口来显示和隐藏状态栏，接下来就来实现相关的功…...

编程日记 2025/4/3 6:50:24

Linux服务器安装MinerU

安装MinerU 为了确保项目的稳定性和可靠性，我们在开发过程中仅对特定的软硬件环境进行优化和测试。这样当用户在推荐的系统配置上部署和运行项目时，能够获得最佳的性能表现和最少的兼容性问题。这里我们以基础的 [[Linux服务器部署PaddleX实战教程]] 使…...

编程日记 2025/5/8 15:32:36

深挖 DeepSeek 隐藏玩法·智能炼金术2.0版本

前引：屏幕前的你还在AI智能搜索框这样搜索吗？“这道题怎么写”“苹果为什么红”“怎么不被发现翘课” ，。看到此篇文章的小伙伴们！请准备好你的思维魔杖，开启【霍格沃茨模式】，看我如何更新秘密的【知识炼金…...

编程日记 2025/5/9 9:31:31

Vite 内联 CSS 和 JS 的解决方案

使用 vite-plugin-singlefile（推荐） 这个插件专门用于将整个 Vite 应用打包成单个 HTML 文件，内联所有 JS 和 CSS。安装 pnpm i vite-plugin-singlefile -D配置 vite.config.js import { defineConfig } from vite import { viteSingleF…...

编程日记 2025/5/9 7:02:04

致敬生物信息学先驱：玛格丽特·戴霍夫（Margaret Dayhoff，1925-1983）

李升伟编译社论发布于：2025年3月11日《自然-计算科学》第五卷第187页（2025年） 在玛格丽特戴霍夫（Margaret Dayhoff，1925-1983）百年诞辰之际，我们聚焦这位先驱在生物信息学领域留下的不朽…...

编程日记 2025/5/9 8:05:04

打开swagger文档报空指针异常 java.lang.NullPointerException: nullat springfox.documentation.oas.mappers.SchemaMapper.model(SchemaMapper.java:97)at springfox.documentation.oas.mappers.SchemaMapper.mapModel(SchemaMapper.java:85)at springfox.documentation.oas…...

编程日记 2025/5/5 22:06:10

笔记2——网络参考模型

一、OSI参考模型： 应用层： 报文给应用程序提供接口表示层： 进行数据格式的转换会话层： 在通讯双方之间建立、管理和终止会话传输层： 数据段；建立、维护、取消一次端到端的数据传输过程；控制…...

编程日记 2025/5/7 13:19:52

Spring AOP + Redis缓存设计实战：基于注解的优雅三防方案（击穿/穿透/雪崩）

文章目录摘要正文一、缓存设计的痛点与破局二、核心代码拆解：四层防御设计1. 注解驱动（ZywCacheable）2. 缓存击穿防护：双重检查锁3. 缓存穿透防护：空值标记4. 缓存雪崩防护：TTL随机算法三、生产环境最佳…...

编程日记 2025/5/6 13:30:43

洛谷题单3-P5720 【深基4.例4】一尺之棰-python-流程图重构

题目描述《庄子》中说到，“一尺之棰，日取其半，万世不竭”。第一天有一根长度为 a a a 的木棍，从第二天开始，每天都要将这根木棍锯掉一半（每次除 2 2 2，向下取整）。第几天的时候木…...

编程日记 2025/5/7 17:33:25

jdk21新特性详解使用总结

jdk21新特性详解总结 1.StringBuilder和StringBuffer新增了一个repeat方法 /*** Java 21的StringBuilder和StringBuffer新增了一个repeat方法*/public static void repeatStr(){var sbnew StringBuilder().repeat("*",10);System.out.println(sb);}运行结果如下&…...

编程日记 2025/5/7 5:22:13

解码 collections.Counter - 频率统计的利器

文章目录前言一、什么是 collections.Counter？二、基本用法：从创建到访问2.1 创建 Counter 对象2.2 访问计数三、核心功能：更新与排序3.1 更新计数3.2 获取常见元素四、高级用法：数学运算与转换4.1 数学运算4.2 类型转换五、实际应用：Counter 的威力5.1 词频统计5.2 在…...

编程日记 2025/4/26 22:14:42

Mysql基础笔记

# 1.SQL数据类型可以去这篇文章看看： 最全 SQL 字段类型（4种）、属性（6种）总结:https://blog.csdn.net/weixin_45654582/article/details/119157403 ### 一.整数类型 ### 二.小数类型(2种) 1、浮点型：…...

编程日记 2025/5/3 19:40:55

HttpClient-03.入门案例-发送POST方式请求

一.发送POST方式请求编写代码： 1.创建一个HttpClient对象 2.创建一个HttpGet请求 3.发送http的get请求并获得响应对象 4.通过发送GET请求获取的CloseableHttpResponse响应对象来获取状态码以及响应数据 package com.sky.test;import com.alibaba.fastjson.JS…...

编程日记 2025/4/30 19:34:50

Oracle数据库数据编程SQL＜3.6 PL/SQL 包(Package)＞

包是Oracle数据库中一种重要的PL/SQL程序结构，它将逻辑相关的变量、常量、游标、异常、过程和函数组织在一起，提供了更好的封装性和模块化。在大型项目中，可能有很多模块，而每一个模块又有自己的存过、函数等。而这些存过、函数默…...

编程日记 2025/5/5 8:06:42

每日一题---买卖股票的最好时机(一)、(二)

目录买卖股票的最好时机(一) 一、题目链接：买卖股票的最好时机(一)_牛客题霸_牛客网二、解题思路三、代码实现买卖股票的最好时机（二） 一、题目链接：买卖股票的最好时机(二)_牛客题霸_牛客网编辑二、解题思路 …...

编程日记 2025/5/6 21:26:11

XSS漏洞的分类解释和演示实验

XSS漏洞：跨站脚本攻击(cross site scripting)，为了不和CSS混淆而改名。攻击者网web插入恶意script代码，当用户浏览页面时，嵌入的代码会被执行。危害：盗取各类用户，强制发送电子邮件，网站挂马等…...

编程日记 2025/5/8 21:06:43

【Pandas】pandas DataFrame info

Pandas2.2 DataFrame Attributes and underlying data 方法描述DataFrame.index用于获取 DataFrame 的行索引DataFrame.columns用于获取 DataFrame 的列标签DataFrame.dtypes用于获取 DataFrame 中每一列的数据类型DataFrame.info([verbose, buf, max_cols, …])用于提供 Dat…...

编程日记 2025/5/8 5:01:56

JP1 Systemwalker 和 unirita的A-AUTO制品对比

以下是 JP1 SystemWalker（日立） 与 Unirita A-AUTO 的对比分析。两者均为日本企业开发的IT运维自动化工具，但在功能定位、技术架构和适用场景上存在显著差异： 1. 产品背景与市场定位维度JP1 SystemWalkerUnirita A-AUTO开发商日…...

编程日记 2025/4/30 20:41:06

探索鸿蒙操作系统：迎接万物互联新时代

# 探索鸿蒙操作系统：迎接万物互联新时代在科技飞速发展的当下，万物互联的时代浪潮正席卷而来。在这个全新的时代背景下，移动应用开发领域面临着前所未有的挑战，同时也迎来了诸多机遇。而鸿蒙操作系统（HarmonyOS&…...

编程日记 2025/5/1 17:10:30

NOIP2010提高组.引水入城

*前置题目 901. 滑雪 #include <iostream> #include <algorithm> #include <cstring>using namespace std;const int N 310, INF 0x3f3f3f3f; const int dx[4] {0, -1, 0, 1}, dy[4] {1, 0, -1, 0};int n, m, h[N][N]; int f[N][N]; int ans;int dfs(i…...

编程日记 2025/5/5 9:06:05

NLP高频面试题（二十九）——大模型解码常见参数解析

在大语言模型的实际应用中，如何更有效地控制文本生成的质量与多样性，一直是热门研究话题。其中，模型解码（decode）策略至关重要，涉及的主要参数包括 top_k、top_p 和 temperature 等。本文将详细介绍这些常见…...

编程日记 2025/5/3 9:50:53

【AI产品分享】面向图片的原始位置翻译功能

1. 背景在撰写文字材料时，往往需要配套图像以增强表达效果。然而，有时自己绘制的图可能达不到理想的质量，而在其他文献材料中却能发现更清晰、直观的示例。希望在“站在巨人的肩膀上”优化自己的图像时，通常希望在保留原始图像的…...

编程日记 2025/5/6 5:44:47

为什么要为 REST API 添加认证

在不断发展的 Web 服务领域，REST API 在各种软件系统之间的通信中扮演着至关重要的角色。然而，强大的功能也伴随着巨大的责任。确保敏感数据的安全性和通信的可靠性是至关重要的。这时，认证就显得尤为重要。通过使用认证，我们可以…...

编程日记 2025/5/7 8:49:14

AI 数字人短视频数字人源码部署揭秘：开启虚拟内容创作新纪元

在当下短视频盛行的时代，AI 数字人短视频以其独特的魅力吸引着大众的目光。虚拟偶像在舞台上活力四射，电商平台中数字人不知疲倦地推荐产品，这些令人瞩目的表现背后，源码的部署起着至关重要的作用。它如同幕后的神奇工匠&#xff…...

编程日记 2025/5/6 8:38:59

佳能imageRUNNER 2206N基本参数及管理员密码

基本参数： 产品类型激光数码复合机颜色类型黑白涵盖功能复印/打印/扫描速度类型低速最大原稿尺寸 A3 复印/打印方式激光静电转印方式感光材料 OPC 显影系统干式单组分显影定影…...

编程日记 2025/4/14 17:27:36

【Linux篇】探索进程地址空间：计算机背后的虚拟世界

进程地址空间的奥秘：让你理解程序如何在计算机中生存一. 程序地址空间1.1 基本概念1.2 虚拟内存管理1.3 为什么存在虚拟地址空间1.3.1 意义 2. 最后本文将介绍进程地址空间的基本概念与结构，帮助读者理解操作系统如何管理和分配内存。进程地址空间指的…...

编程日记 2025/5/7 13:35:28

Docker部署sprintboot后端项目

创建Docker网络 docker network create icjs 部署Redis docker run -d \--network icjs \--name redis \-p 6379:6379 \redis:latest数据持久化 docker run --restartalways --network icjs -p 6379:6379 --name redis -v /opt/docker/redis/redis.conf:/etc/redis/redis.c…...

编程日记 2025/5/3 10:42:58

1.4 基于模拟退火改进蛇算法优化VGG13SE网络超参数的故障诊断模型

本博客来源于CSDN机器鱼，未同意任何人转载。更多内容，欢迎点击本专栏，查看更多内容。目录 0 引言 1 改进原理 2 本文改进方法 3 改进蛇优化VGG13SE的故障诊断模型 4 结语 0 引言在【博客】中，我们采用了蛇算法来对VGG1…...

编程日记 2025/5/5 12:41:22

Vue + Scss项目中实现自定义颜色主题的动态切换

当时面试的时候遇到面试官问的一个问题如何实现自定义颜色主题切换,当时我做的只是elementUIPlus提供的暗黑和默认主题切换 theme.scss // 增加自定义主题类型 $themes: (light: (/* 原有配置保持不变 */),dark: (/* 原有配置保持不变 */),custom: () // 空映射…...

编程日记 2025/5/4 7:40:15

C#实现HiveQL建表语句中特殊数据类型的包裹

用C#实现搜索字符串中用’(‘和’)‘包裹的最外层的里面里面的字符串，将里面的记录按一个或多个空格、换行或tab，或者是它的在一起的组合作为分隔，分隔出多个字符串组，如果组中有字符串中同时包含’<‘和’>’，则…...

编程日记 2025/5/7 2:48:24

27 python 标准库概览

在办公室里，每个员工都有一套预装的办公软件：Word 处理文档、Excel 制作表格、Outlook 收发邮件... Python 的标准库就像公司预装的 "办公全家桶"，包含 100 多个模块，覆盖文件操作、时间管理、数据分析等日常需求，无需额外安装即可直接使用。一、文件管理 1.…...

编程日记 2025/4/23 0:23:44

whisper 语音识别的安装与使用

Whisper 是由OpenAI开发的开源自动语音识别（ASR）模型，不仅支持音频转录，还可以用于视频转录。通过调用ffmpeg处理视频，支持主流音视频格式的转录‌。安装安装ffmpeg：下载ffmpeg，Releases B…...

编程日记 2025/4/28 13:57:18

搜广推校招面经六十四

滴滴搜推算法一、定义一个树结构、特征结构。写一个决策树对样本打分逆天啊，上来就是暴击 import numpy as np class TreeNode:def __init__(self, feature_indexNone, thresholdNone, leftNone, rightNone, scoreNone):self.feature_index feature_index #…...

编程日记 2025/5/6 17:25:31

zabbix监控网站（nginx、redis、mysql）

目录前提准备： zabbix-server主机配置： 1. 安装数据库 nginx主机配置： 1. 安装nginx redis主机配置： 1. 安装redis mysql主机配置： 1. 安装数据库 zabbix-server： 1. 安装zabbix 2. 编辑配置文…...

编程日记 2025/5/6 17:25:34

动态规划，如何应用动态规划解决实际问题？

一、动态规划核心概念动态规划是一种分阶段解决问题的数学方法，它将复杂问题分解为更小的子问题，通过存储子问题的解来避免重复计算。关键特征： 最优子结构：问题的最优解包含子问题的最优解重叠子问题：问题可…...

编程日记 2025/5/7 1:33:40

常见操作系统特点及区别对比

操作系统名称类型特点主要用途许可证类型内核类型Windows桌面/服务器图形界面友好，软件生态丰富，闭源个人电脑、企业办公专有商业许可混合内核macOS桌面 (Unix-like)高度优化的硬件整合，Unix基础，闭源创意设计、开发专有商业许可混…...

编程日记 2025/5/1 17:10:27

【资讯分享】为Apple Intelligence打造的有效屏障：“隐私保护气泡”

导读：苹果在WWDC大会上推出Apple Intelligence，主打个性化智能服务，深度整合iOS生态，支持跨App操作与内容感知。通过本地计算与私密云计算（PCC）技术实现端到端加密，确保数据匿名化处理与高透明度…...

编程日记 2025/5/2 22:55:09

AT_abc306_b [ABC306B] Base 2

题目描述给定一个长度为64的序列A(A\_0,A\_1,\dots,A\_{63})A(A_0,A_1,…,A_63)，由0和1组成。求A\_0 2^0 A\_1 2^1 \dots A\_{63} 2^{63}A_020A_121⋯A_63263。约束条件 A\_iA_i是0或1。输入从标准输入中以以下格式给出输入： A_0A0 A_1A…...

编程日记 2025/5/8 14:28:56

C++IO流类库

一、输入输出流(I/O strea) 编译系统已经以运算符或函数的形式做好了对标准外设（键盘、屏幕、打印机、文件）的接口，使用时只需按照要求的格式调用即可。 cin>>x; cout<<x; cin.get(ch); C语言的I/O系统向用户提供一个统一…...

编程日记 2025/5/9 9:14:47

常见的锁策略+synchronized（特性解释）

该篇文章主要是对常见的锁策略的总结（主要的作用是扫盲），如想要了解其他部分，这部分可以不用看目录一、常见的锁策略1. 悲观锁vs乐观锁举例： 2. 重量级锁vs轻量级锁3. 挂起等待锁vs自旋锁举例 4.普通互斥锁vs读写锁…...

编程日记 2025/5/6 8:38:00

spring打包，打包错误

打包(idea) 通过点击井盖样式的符号可以将test测试类取消打包进去点击“M”，双击package即可打包打包出错 ❯ java -jar /home/ying/Documents/java_workspace/spring-01-ioc/target/spring-01-ioc-0.0.1-SNAPSHOT.jar Error: LinkageError occurred while loadi…...

编程日记 2025/5/5 10:41:03

【Linux系统】进程间通信-System V消息队列

🎁个人主页：我们的五年 🔍系列专栏：Linux网络编程 🌷追光的人，终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章 Linux网络系列文章计算机网络（Linux网…...

编程日记 2025/5/8 10:42:58

DeepSeek×擎创科技：当智能运维遇见大模型「懂行」革命

运维人最懂「动态阈值」的痛在数字化转型浪潮中，运维监控正经历从"人工经验"到"智能决策"的跃迁。传统动态阈值设置依赖人工分析历史数据、反复调整规则的模式，既难以应对业务波动性，又消耗大量技术资源。擎创科技基…...

编程日记 2025/5/6 13:44:36

手绘风格流程图工具：简单高效的在线流程图绘制工具

手绘风格流程图：简单高效的在线流程图绘制工具 🎉 项目介绍大家好！我很高兴向大家分享我最近开发的一个项目 —— 在线绘制手绘风格流程图，这是一个简单高效的在线流程图绘制工具。无论是整理思路、规划项目还是准备演示&#…...

编程日记 2025/4/28 9:20:08

leetcode287.寻找重复数

与寻找链表环的起始点一样 ，用快慢指针让二者相遇后，慢指针回到起始点二者以同样速度移动最终会在环的起始点相遇 class Solution {public int findDuplicate(int[] nums) {int slow nums[0], fast nums[0];do {slow nums[slow];fast nums[nums[fas…...

编程日记 2025/4/25 12:36:28