2025华为暑期实习校招准备帖

写在前面
机考筹备

大致规划
以下是正题

1. DFS

模板
思索
真题

2025B DFS 返回矩阵中非1的元素个数 200分
2025B DFS 欢乐周末 200分

2. BFS

模板
思索
真题

2025B BFS 返回矩阵中非1的元素个数 200分
2025B BFS 欢乐周末 200分

写在前面

博主申请2025华为菁英班暑期实习项目，此贴开始编写于机考前十天。

机考筹备

机考ACM形式，一般为每周三19:00 – 21:00；录屏，在线测试，可以使用本地IDE；
三道题100，200，300，但难度不一定按顺序，尝试使用暴力、打表等骗分技巧；
150分即通过机考，可以无限次测评，可以看到得分情况，不能看到测试用例。
常见考点：DFS、BFS、排序、二分、双指针、模拟、字符串、动态规划、图论、数据结构。

大致规划

DFS、BFS一定熟练，动态规划掌握常见的几种（博主经常感觉状转方程像是从天上掉下来的，可能智商不够），图论（最短路、缩点、树的操作）、数据结构（栈、队列、并查集）、字符串（KMP）。
复习方向：模板+真题，下文整理也如此。
重点：DFS、BFS
次重点：排序、二分、双指针、模拟、动态规划
次次重点：字符串、图论、数据结构
以上排列顺序，主要是博主的主观判断，基于在有限的时间优先复习性价比较高的内容的想法。
模板内容参考了《手写代码必备手册(C++版)》一文。

以下是正题

1. DFS

模板

/*
input 输入数据指针
path 当前路径，也是中间结果
result 存放最终结果
return 路径长度，如果是求路径本身，则不需要返回长度
*/

void dfs(type *input, type *path, int cur or gap, type *result) {
	if(数据非法) return 0; // 终止条件

	if(cur == input.size( or gap == 0)) { // 收敛条件
		将path放入result
	}

	if(可以剪枝) return;

	for(...) { // 执行所有可能的扩展动作
		执行动作，修改path
		dfs(input, step + 1 or gap--, result);
		恢复path
	}
}

思索

适用场景：单链表、二叉树、集合等递归数据结构；
状态转换图：树或者图
对于求解目标：如果必须走到最深才能得到一个解，那显然符合深搜。

深搜常见三个问题：
（1）求可行解总数
（2）求一个可行解
（3）求所有可行解

思考步骤：

判断求解问题，如果求路径本身，则添加path[]数组；如果求路径条数则不需要存储路径。
求一个解，找到即可停止；求所有解，找到一个解后继续扩展。
如何表示状态？
如何扩展状态？
判重：状态转换图是树，无需判重；若为图，需判重。
终止条件？树，叶子节点；图，出度为0结点。
收敛条件？即合法解情况，正向深搜，判断是否到达目标状态；逆向深搜，判断是否到达初始状态。
考虑剪枝和记忆化搜索？

真题

2025B DFS 返回矩阵中非1的元素个数 200分

题目描述
存在一个m*n的二维数组，其成员取值范围为0，1，2。其中值为1的元素具备同化特性，每经过1S，将上下左右值为0的元素同化为1。而值为2的元素，免疫同化。将数组所有成员随机初始化为0或2，再将矩阵的[0, 0]元素修改成1，在经过足够长的时间后求矩阵中有多少个元素是0或2（即0和2数量之和）。

输入描述
输入的前两个数字是矩阵大小。后面是数字矩阵内容。

输出描述
返回矩阵中非1的元素个数。

歪楼：这个好像是BFS的题目，不过DFS也可以实现。
思路：

相当于走迷宫，从(0,0)出发可以走到哪些点，把0看作可走的点，2看作墙壁即可。

代码

#include<bits/stdc++.h>

using namespace std;
int n,m;
int cnt;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int maze[1100][1100];
bool visited[1100][1100];

int cango(int x, int y) {
	for(int i = 0;i < 4;i++) {
		int u = x+dx[i];
		int v = y+dy[i];
		if(u > -1 && u < n && v > -1 && v < m && !visited[u][v] && maze[u][v] == 0) {
			return i;
		}
	}
	return 5;
}

void dfs(int x,int y) {
	if(x == 0 && y == 0 && cango(x,y) == 5)
		return;

	for(int i = 0;i < 4;i++) {
		int u = x+dx[i];
		int v = y+dy[i];
		if(u > -1 && u < n && v > -1 && v < m && !visited[u][v] && maze[u][v] == 0) {
			maze[u][v] = 1;
			visited[u][v] = 1;
			cnt++;
			dfs(u,v);
		}
	}

}

int main() {

	std::cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j = 0;j < m;j++) {
			std::cin >> maze[i][j];
		}
	}

	maze[0][0] = 1;
	visited[0][0] = 1;
	cnt++;
	dfs(0,0);
	std::cout << m*n-cnt;
	return 0;
}

2025B DFS 欢乐周末 200分

题目描述
小华和小为是很要好的朋友，他们约定周末一起吃饭。通过手机交流，他们在地图上选择了多个聚餐地点（由于自然地形等原因，部分聚餐地点不可达），求小华和小为都能到达的聚餐地点有多少个？

输入描述
第一行输入 m 和 n。m 代表地图的长度。n 代表地图的宽度

第二行开始具体输入地图信息，地图信息包含：

0 为通畅的道路
1 为障碍物（且仅1为障碍物）
2 为小华或者小为，地图中必定有且仅有2个（非障碍物）
3 为被选中的聚餐地点（非障碍物）
备注
地图的长宽为 m 和 n，其中：

4 ≤ m ≤ 100
4 ≤ n ≤ 100
聚餐的地点数量为 k，则

1< k ≤ 100
输出描述
可以被两方都到达的聚餐地点数量，行末无空格。

思路：

依然走迷宫，双向DFS，博主记得好像有双向BFS，暂时先用DFS写了。

代码：

#include<bits/stdc++.h>

using namespace std;
int n,m;
int cnt[2];
int mark_x[1100][2],mark_y[1100][2];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int maze[1100][1100];
int start_x[2],start_y[2];
bool visited[1100][1100];

int cango(int x, int y) {
	for(int i = 0;i < 4;i++) {
		int u = x+dx[i];
		int v = y+dy[i];
		if(u > -1 && u < n && v > -1 && v < m && !visited[u][v] && maze[u][v] != 1) {
			return i;
		}
	}
	return 5;
}

void dfs(int x,int y,int player) {
	if(x == start_x[player] && y == start_y[player] && cango(x,y) == 5)
		return;

	for(int i = 0;i < 4;i++) {
		int u = x+dx[i];
		int v = y+dy[i];
		if(u > -1 && u < n && v > -1 && v < m && !visited[u][v] && maze[u][v] != 1) {
			visited[u][v] = 1;
			if(maze[u][v] == 3) {
				mark_x[cnt[player]][player] = u;
				mark_y[cnt[player]++][player] = v;
			}
			dfs(u,v,player);
		}
	}

}

int main() {

	std::cin >> n >> m;
	int player = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0;j < m;j++) {
			std::cin >> maze[i][j];
			if(maze[i][j] == 2) {
				start_x[player] = i;
				start_y[player++] = j;
			}
		}
	}

	visited[start_x[0]][start_y[0]] = 1;
	dfs(start_x[0],start_y[0],0);
	memset(visited,0,sizeof(visited));
	visited[start_x[1]][start_y[1]] = 1;
	dfs(start_x[1],start_y[1],1);

	int ans = 0;
	for(int i = 0; i < cnt[0]; i++) {
		for(int j = 0; j < cnt[1]; j++) {
			if(mark_x[i][0] == mark_x[j][1] && mark_y[i][0] == mark_y[j][1])
				ans++;
		}
	}

	std::cout << ans;
	return 0;
}

2. BFS

题目无规律，不能用分治、贪心、动规，即用搜索。
广搜包括普通广搜、双向广搜、A*搜索。

模板

/*
反向生成路径
father 树
target 目标结点
return 从起点到target的路径
*/

template<typename state_t>
vector<state_t> gen_path(const unordered_map<state_t, state_t> &father, 
		const state_t &target) {
	vector<state_t> path;
	path.push_back(target);

	state_t cur = target;
	while(father.find(cur) != father.end()) {
		cur = father.at(cur);
		path.push_back(cur);
	}
	reverse(path.begin(), path.end());

	return path;
	
};

/*
广搜
state_t 状态，如整数，字符串，一维数组等
start 起点
state_is_target 判断状态是否是目标的函数
state_extend 状态扩展函数
return 从起点到目标状态的一条最短路径
*/

template<typename state_t>
vector<state_t> bfs(state_t &start, bool (*state_is_target)(const state_t&), 
		vector<state_t>(*state_extend)(const state_t&,
				unordered_set<string> & visited)) {
	queue<state_t> next, current;
	unordered_set<state_t> visited;
	unordered_map<state_t, state_t> father;

	int level = 0;
	bool found = false;
	state_t target;

	current.push(start);
	visited.insert(start);
	while(!current.empty() && !found) {
		++level;
		while(!current.empty() && ! found) {
			const state_t state = current.front();
			current.pop();
			vector<state_t> new_states = state_extend(state, visited);
			for(auto iter = new_states.begin();
					iter != new_states.end() && ! found; ++iter) {
				const state_t new_state(*iter);

				if(state_is_target(new_state)) {
					found = true;
					target = new_state;
					father[new_state] = state;
					break;
				}
				next.push(new_state);
				father[new_state] = state;
			}
		}
		swap(next, current);
	}

	if(found) {
		return gen_path(father, target);
		// return level + 1;
	} else {
		return vector<state_t>();
		//return 0;
	}
}

思索

适用场景
输入数据： 没有“递归”的特征，树或者图。
状态转换图： 树或者图。
求解目标： 求最短

思考步骤：

求路径长还是求路径本身？求路径长，状态里存储路径长度；求路径本身：
（1）用一棵树存储宽搜过程中的路径；
（2）预估状态个数总数，开一个大数组，用树的双亲表示法存储
如何表示状态？一般记录当前位置或者整体局面。
如何扩展状态？
判重：使用哈希
（1）使用通用的哈希表unordered_set判重
（2）开一个大布尔数组，作为哈希表判重
目标状态是否已知？正向广搜，逆向广搜，双向广搜。

真题

2025B BFS 返回矩阵中非1的元素个数 200分

代码

#include<bits/stdc++.h>

using namespace std;
int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int BFS(std::vector<std::vector<int>>& maze)
{
	int count = 1;
	maze[0][0] = 1;
	std::queue<std::pair<int, int>> q;
	q.push({0,0});

	while(!q.empty())
	{
		std::pair<int, int> tmp = q.front();
		q.pop();
		int x = tmp.first;
		int y = tmp.second;
		for(int i = 0;i < 4;i++)
		{
			int u = x+dx[i];
			int v = y+dy[i];
			if(u > -1 && u < n && v > -1 && v < m && maze[u][v] == 0)
			{
				maze[u][v] = 1;
				count++;
				q.push({u,v});
			}
		}
	}
	return count;
}

int main()
{
	std::cin >> n >> m;
	std::vector<std::vector<int>> maze(n,vector<int>(m));
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			std::cin >> maze[i][j];
		}
	}
	int count = BFS(maze);
	std::cout << m*n-count;
	return 0;
}

2025B BFS 欢乐周末 200分

代码

#include<bits/stdc++.h>

using namespace std;

int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

void BFS(vector<vector<int>>& maze, vector<vector<bool>>& visited,int x,int y)
{
	visited[x][y] = 1;
	std::queue<std::pair<int,int>> q;
	q.push({x,y});
	while(!q.empty())
	{
		std::pair<int,int> tmp = q.front();
		q.pop();
		int row = tmp.first;
		int col = tmp.second;

		for(int i = 0;i < 4;i++)
		{
			int u = row+dx[i];
			int v = col+dy[i];
			if(u > -1 && u < n && v > -1 && v < m && !visited[u][v] && maze[u][v] != 1)
			{
				visited[u][v] = 1;
				q.push({u,v});
			}  
		}
	}
}

int main()
{
	std::cin >> n >> m;
	std::vector<std::vector<int>> maze(n,std::vector<int>(m));
	std::vector<pair<int,int>> starts;
	std::vector<pair<int,int>> ends;

	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			std::cin >> maze[i][j];
			if(maze[i][j] == 2)
			{
				starts.push_back({i,j});
			}
			if(maze[i][j] == 3)
			{
				ends.push_back({i,j});
			}
		}
	}

	std::vector<std::vector<bool>> visited1(n,std::vector<bool>(m,false));
	pair<int,int> start1 = starts[0];
	BFS(maze, visited1, start1.first, start1.second);

	std::vector<std::vector<bool>> visited2(n,std::vector<bool>(m,false));
	pair<int,int> start2 = starts[1];
	BFS(maze, visited2, start2.first, start2.second);

	int res = 0;

	for(int i = 0;i < (int)ends.size();i++)
	{
		pair<int,int> end = ends[i];
		int x = end.first;
		int y = end.second;
		if(visited1[x][y] && visited2[x][y])
			res++;
	}
	std::cout << res;
	return 0;
}

文章版权归作者所有，未经允许请勿转载。如内容涉嫌侵权，请在本页底部进入<联系我们>进行举报投诉!

THE END