最新华为OD机试真题-K小姐和A先生的聚餐计划(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> K小姐和A先生的聚餐计划(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

✈️ K小姐和A先生的聚餐计划

问题描述

K小姐和A先生是很要好的朋友。他们约定周末一起吃饭,通过手机在地图上选择了多个聚餐地点。但由于一些障碍物的存在,部分聚餐地点可能无法到达。现在给定一张地图,请你帮助他们找出有多少个聚餐地点是两人都能到达的。

输入格式

第一行包含两个正整数 和 ,表示地图的长度和宽度。()

接下来的 行,每行包含 个整数,表示地图的具体信息。其中:

• 表示通畅的道路
• 表示障碍物(地图上只有 表示障碍)
• 表示K小姐或A先生的初始位置,地图中有且仅有 个
• 表示两人选择的聚餐地点,保证不是障碍并且数量在 到 之间

输出格式

一个整数,表示两人都能到达的聚餐地点的数量。

样例输入

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

样例输出

2

样例输入

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

样例输出

0

数据范围

• 
• 聚餐地点数量在 到 之间
• 障碍物在地图上用 表示,非障碍物不会是
• 保证有且仅有 个初始位置

题解

本题可以用 BFS 来解决。我们分别从K小姐和A先生的位置开始进行 BFS 遍历,对于每个遍历到的聚餐地点,将其记录在一个哈希表中,哈希表的键为聚餐地点的坐标,值为能到达该地点的人数。

遍历结束后,我们再遍历哈希表,统计所有值为 的键的数量,即为两人都能到达的聚餐地点数量。

时间复杂度 ,空间复杂度 。

参考代码

• Python

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = {}

def bfs(x, y, vis):
    queue = [(x, y)]
    vis[x][y] = 1
    while queue:
        x, y = queue.pop(0)
        if grid[x][y] == 3:
            res[(x, y)] = res.get((x, y), 0) + 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and vis[nx][ny] == 0 and grid[nx][ny] != 1:
                queue.append((nx, ny))
                vis[nx][ny] = 1

for i in range(n):
    for j in range(m):
        if grid[i][j] == 2:
            bfs(i, j, [[0] * m for _ in range(n)])

ans = sum(1 for v in res.values() if v > 1)
print(ans)

• Java

import java.util.*;

public class Main {
    static int n, m;
    static int[][] grid;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static Map<String, Integer> res = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        grid = new