字节校招，这所 211 打败清华北大！

大家好，我是吴师兄。

众所周知，很多大型公司为了品牌效应和招到最优秀最适合自己公司的人才，往往都会去各大高校线下宣传和招聘，而它们最青睐的就是去一些 985 院校， 比如最近字节就会在国内的 10 个城市中的 18 所院校里面进行宣讲，其中 16 个院校都是 985 院校，只有 2 所院校是 211，其中一所是北邮 。

或许很多程序员都知道，不少互联网大厂都喜欢招聘北邮的同学，同时根据字节跳动的数据， 北邮的校招生在技术岗位上数量排名第一 ，超过了国内最顶尖的清华大学和北京大学。

这一现象背后的原因可以归结为北邮在相关技术领域的强大实力和精准的行业对接，北邮的 计算机科学 和 电子科学与技术 这两个专业非常强，在教育部的第四轮学科评估中，得到了A的高分，说明它们在全国范围内也是数一数二的。这两个专业都是北邮的王牌，正因为这些强大的学科背景，北邮的学生在互联网大厂的校招中非常受欢迎，比很多985学校的学生还要抢手。

另外，虽然清华、北大是国内数一数二的顶尖名校，但它们的学生选择的职业方向更广，很多人不一定非得进入IT行业。

而北邮则不同，它的重点就在信息技术和通信领域，所以毕业生更多专注于互联网行业，这就是为什么北邮的校招生在IT行业数量上领先的原因 。

...

回归我们公众号的主题。

继续来一道和「大厂秋招」相关的算法原题。

2024 年的大厂真题可以在我的网站上进行练习。

网站地址： https://oj.algomooc.com/

关注吴师兄，算法学习好轻松

题目描述

网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。

注意:网络信号可以绕过阻隔物

1、 array[m][n] 的二维数组代表网格地图，

2、 array[i][j] = 0 代表 i 行 j 列是空旷位置;

3、 array[i][j] = x ( x 为正整数)代表 i 行 j 列是信号源，信号强度是 x ;

4、 array[i][j] = -1 代表 i 行 j 列是阻隔物.

5、信号源只有 1 个，阻隔物可能有 0 个或 多 个

6、网络信号衰减是上下左右相邻的网格衰减 1

7、现要求输出对应位置的网络信号值。

输入

输入为三行：

第一行为 m 、 n ，代表输入是一个 m × n 的数组。

第二行是一串 m × n 个用空格分隔的整数。每连续 n 个数代表一行，再往后 n 个代表下一行，以此类推。对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物。

第三行是 i 、 j ，代表需要计算 array[i][j] 的网络信号值。注意:此处 i 和 j 均从 0 开始，即第一行 i 为 0

例如

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4

代表如下地图

需要输出第 1 行第 4 列的网络信号值，如下图，值为 2

输出

输出对应位置的网络信号值，如果网络信号未覆盖到，也输出 0。

一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值。

示例一

输入

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4

输出

2

示例二

输入

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
2 1

输出

0

备注

1. m 不一定等于 n ， m < 100 ， n < 100 ,网络信号小于 1000 。
2. 信号源只有 1 个，阻隔物可能有 0 个或多个。
3. 输入的 m ， n 与第二行的数组是合法的，无需处理数量对不上的异常情况。
4. 要求输出信号值的位置，不会是阻隔物。

解题思路

注意，本题和LC994. 腐烂的橘子几乎完全一致，属于计算BFS层数的问题，而且只有一个信号源，所以使用常规的单源BFS方法即可完成。

要注意以下几点：

• 输入的数据是一个长度为 m*n 的一维数组，需要转换成我们常用的 grid 二维矩阵。
• 本题可以直接在 grid 上进行元素修改，最终输出要求的点 (target_x, target_y) 的强度值 grid[target_x][target_y] 即可。
• 由于直接对 grid 进行修改，如果某个点的强度已经从 0 修改为其他值，说明已经进入过，故无需重复使用 checkList 进行检查。
• 搜索层数可以从信号源的强度 intensity 不断 -1 来判断，无需从 level = 0 开始递增。