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

华为OD机试_2025 B卷_欢乐的周末（Python，100分）（附详细解题思路）

news 2025/6/5 19:05:49

题目描述

小华和小为是很要好的朋友，他们约定周末一起吃饭。

通过手机交流，他们在地图上选择了多个聚餐地点（由于自然地形等原因，部分聚餐地点不可达），求小华和小为都能到达的聚餐地点有多少个？

输入描述
第一行输入 m 和 n

m 代表地图的长度
n 代表地图的宽度
第二行开始具体输入地图信息，地图信息包含：

0 为通畅的道路
1 为障碍物（且仅1为障碍物）
2 为小华或者小为，地图中必定有且仅有2个（非障碍物）
3 为被选中的聚餐地点（非障碍物）
输出描述
可以被两方都到达的聚餐地点数量，行末无空格。

备注
地图的长宽为 m 和 n，其中：

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

1< k ≤ 100
用例

输入

4 4
2 1 0 3
0 1 2 1
0 3 0 0
0 0 0 0

输出

说明

第一行输入地图的长宽为3和4。

第二行开始为具体的地图，其中：3代表小华和小明选择的聚餐地点；2代表小华或者小明（确保有2个）；0代表可以通行的位置；1代表不可以通行的位置。

此时两者能都能到达的聚餐位置有2处。

输入

4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0

输出

说明

第一行输入地图的长宽为4和4。

由于图中小华和小为之间有个阻隔，此时，没有两人都能到达的聚餐地址，故而返回0。

解题思路：双源点广度优先搜索

这道题要求找出两个朋友都能到达的聚餐地点数量。解决问题的关键在于准确模拟两个人的移动范围，并找到他们可达区域的交集。以下是分步解析：

核心思路图解

1. 问题本质

地形特征：地图中存在两种特殊标记
- 2：表示小华和小为的初始位置
- 3：表示目标聚餐地点
移动规则：每次可以向上下左右四个方向移动，遇到障碍物（1）则无法通过
最终目标：找出所有同时被两人可达的3的位置

2. 关键观察

独立搜索：需要分别计算两人的可达区域
集合运算：最终结果是两人可达3的交集数量
高效搜索：广度优先搜索（BFS）天然适合模拟扩散过程

3. 算法选择

采用双BFS搜索的原因：

能够准确记录每个起点的可达区域
时间复杂度O(2×m×n)，完全满足题目数据范围
使用集合运算快速求交集

实现步骤详解

步骤一：定位初始位置

遍历整个矩阵，记录所有值为2的坐标。根据题目要求，必定能找到且仅有两个起点。

# 示例代码段：寻找初始位置
starts = []
for i in range(m):for j in range(n):if grid[i][j] == 2:starts.append((i, j))
src1, src2 = starts

步骤二：BFS可达区域计算

对每个起点执行标准BFS算法：

初始化队列和访问标记集合
记录所有经过的3的位置
使用四个方向向量进行扩散

from collections import dequedef bfs(start_x, start_y):visited = set()queue = deque([(start_x, start_y)])visited.add((start_x, start_y))targets = set()directions = [(-1,0), (1,0), (0,-1), (0,1)]while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x + dx, y + dy# 边界检查 + 障碍物检查 + 访问状态检查if 0 <= nx < m and 0 <= ny < n:if (nx, ny) not in visited and grid[nx][ny] != 1:visited.add((nx, ny))if grid[nx][ny] == 3:targets.add((nx, ny))queue.append((nx, ny))return targets

步骤三：结果统计

计算两个可达集合的交集大小：

set1 = bfs(src1[0], src1[1])
set2 = bfs(src2[0], src2[1])
print(len(set1 & set2))

代码实现与解析

from collections import deque# 读取输入
m, n = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]# 查找初始位置
starts = []
for i in range(m):for j in range(n):if grid[i][j] == 2:starts.append((i, j))
src1, src2 = starts# BFS函数定义
def find_reachable(start):visited = set([start])queue = deque([start])reachable = set()dirs = [(-1,0),(1,0),(0,-1),(0,1)]while queue:x, y = queue.popleft()for dx, dy in dirs:nx, ny = x+dx, y+dyif 0<=nx<m and 0<=ny<n:if (nx,ny) not in visited and grid[nx][ny] !=1:visited.add((nx,ny))if grid[nx][ny] ==3:reachable.add((nx,ny))queue.append((nx,ny))return reachable# 计算并输出结果
reach1 = find_reachable(src1)
reach2 = find_reachable(src2)
print(len(reach1 & reach2))