华为OD机试 - 欢乐的周末 - 深度优先搜索dfs算法（Python/JS/C/C++ 2025 B卷 200分）

于 2025-05-13 08:00:42 发布
阅读量374 收藏 6
点赞数 11
分类专栏： 搬砖工逆袭Java架构师 文章标签： 算法 华为od 深度优先 华为OD机试 2025B卷
本文为博主原创文章，未经博主允许不得转载。
本文链接：https://blog.csdn.net/guorui_java/article/details/145031117
版权

在这里插入图片描述

华为OD机试 2025B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

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

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

二、输入描述

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

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

  • 0为通畅的道路
  • 1为障碍物(仅1为障碍物)
  • 2为小华或者小为，地图中必定有且仅有2个(非障碍物)
  • 3为被选中的聚餐地点(非障碍物)

三、输出描述

求小华和小为都能到达的聚餐地点有多少个?

在这里插入图片描述

四、测试用例

测试用例1：

1、输入

2 2
2 3
3 2

2、输出

2

3、说明

地图较小，两人各自位于对角，两个聚餐地点均可互相到达。

测试用例2：

1、输入

3 3
2 1 3
1 1 1
3 1 2

2、输出

0

3、说明

所有聚餐地点都被障碍物包围，小华和小为无法到达任何共同的聚餐地点。

五、深度优先搜索dfs

在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）；

对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。
搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。
产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）。

搜索的要点：

  1. 初始状态；
  2. 重复产生新状态；
  3. 检查新状态是否为目标，是结束，否转（2）；

如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。

如果扩展是首先扩展新产生的状态，则叫深度优先搜索。

深度优先搜索用一个数组存放产生的所有状态。

  1. 把初始状态放入数组中，设为当前状态；
  2. 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；
  3. 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
  4. 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法；
  5. 如果数组为空，说明无解。

六、解题思路

求小华和小为都能到达的聚餐地点有多少个?

转成大白话就是，问有几个3可以满足两个2可以同时到达。

  1. 第一行输入地图的长度m，即m行，地图的宽度n，即n列；
  2. 第二行开始具体输入地图信息；
  3. 地图信息初始化；
  4. 利用深度优先搜索dfs算法，获取符合要求的餐馆；
  5. 定义okNum，记录小华和小为都能到达的聚餐地点有多少个；
  6. 如果没有满足条件的，直接输出0；
  7. 如果存在满足条件的餐馆3，则输出都能到达的聚餐地点个数；

六、Python算法源码

# Python实现

import sys
sys.setrecursionlimit(1000000)

def main():
    import sys
    from collections import defaultdict

    sys.stdin = sys.__stdin__
    m, n = map(int, sys.stdin.readline().split())
    arr = []
    position = []
    for i in range(m):
        row = list(map(int, sys.stdin.readline().split()))
        arr.append(row)
        for j in range(n):
            if row[j] == 2:
                position.extend([i, j])
    map1 = {}
    map2 = {}
    arrX = [-1, 0, 1, 0]
    arrY = [0, 1, 0, -1]

    def get_key(x, y):
        return f"{x}@{y}"

    def dfs(x, y, map_reach):
        if arr[x][y] == 3:
            key = get_key(x, y)
            map_reach[key] = map_reach.get(key, 0) + 1
            return
        k = arr[x][y]
        arr[x][y] = -1  # 标记为已访问
        for i in range(4):
            a = x + arrX[i]
            b = y + arrY[i]
            if 0 <= a < m and 0 <= b < n and arr[a][b] != 1 and arr[a][b] != -1:
                if arr[a][b] == 3:
                    key = get_key(a, b)
                    if key not in map_reach:
                        dfs(a, b, map_reach)
                else:
                    dfs(a, b, map_reach)
        arr[x][y] = k  # 恢复原值

    # 分别对两个人进行DFS
    dfs(position[0], position[1], map1)
    dfs(position[2], position[3], map2)

    # 统计共同可达的聚餐地点
    ok_sum = 0
    if map1 and map2:
        for key in map1:
            if key in map2:
                ok_sum +=1
    print(ok_sum)

if __name__ == "__main__":
    main()

七、JavaScript算法源码

// JavaScript实现

function main() {
    const fs = require('fs');
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    let index = 0;
    const [m, n] = input[index++].split(' ').map(Number);
    const arr = [];
    const position = [];
    for (let i = 0; i < m; i++) {
        const row = input[index++].split(' ').map(Number);
        arr.push(row);
        for (let j = 0; j < n; j++) {
            if (row[j] === 2) {
                position.push(i, j);
            }
        }
    }
    const map1 = new Map();
    const map2 = new Map();
    const arrX = [-1, 0, 1, 0];
    const arrY = [0, 1, 0, -1];

    function getKey(x, y) {
        return `${x}@${y}`;
    }

    function dfs(x, y, mapReach) {
        if (arr[x][y] === 3) {
            const key = getKey(x, y);
            mapReach.set(key, (mapReach.get(key) || 0) + 1);
            return;
        }
        const k = arr[x][y];
        arr[x][y] = -1; // 标记为已访问
        for (let i = 0; i < 4; i++) {
            const a = x + arrX[i];
            const b = y + arrY[i];
            if (a >= 0 && a < m && b >= 0 && b < n && arr[a][b] !== 1 && arr[a][b] !== -1) {
                if (arr[a][b] === 3) {
                    const key = getKey(a, b);
                    if (!mapReach.has(key)) {
                        dfs(a, b, mapReach);
                    }
                } else {
                    dfs(a, b, mapReach);
                }
            }
        }
        arr[x][y] = k; // 恢复原值
    }

    // 分别对两个人进行DFS
    dfs(position[0], position[1], map1);
    dfs(position[2], position[3], map2);

    // 统计共同可达的聚餐地点
    let okSum = 0;
    if (map1.size > 0 && map2.size > 0) {
        for (let key of map1.keys()) {
            if (map2.has(key)) {
                okSum++;
            }
        }
    }
    console.log(okSum);
}

main();

八、C算法源码

**// C语言实现

#include <stdio.h>
#include <string.h>

#define N 110

int arr[N][N];
int m, n;
int position[4];
int arrX[4] = {-1, 0, 1, 0};
int arrY[4] = {0, 1, 0, -1};
int map1[N*N][2];
int map2[N*N][2];
int count1 = 0, count2 = 0;

// 判断两个坐标是否相同
int isSame(int x1, int y1, int x2, int y2){
    return x1 == x2 && y1 == y2;
}

void dfs(int x, int y, int map[][2], int *count){
    if(arr[x][y] == 3){
        map[*count][0] = x;
        map[*count][1] = y;
        (*count)++;
        return;
    }
    int temp = arr[x][y];
    arr[x][y] = -1; // 标记为已访问
    for(int i=0;i<4;i++){
        int a = x + arrX[i];
        int b = y + arrY[i];
        if(a >=0 && a < m && b >=0 && b < n && arr[a][b] !=1 && arr[a][b]!=-1){
            dfs(a, b, map, count);
        }
    }
    arr[x][y] = temp; // 恢复原值
}

int main(){
    scanf("%d %d", &m, &n);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d", &arr[i][j]);
            if(arr[i][j]==2){
                position[count1*2] = i;
                position[count1*2+1] = j;
                count1++;
            }
        }
    }
    // DFS for first person
    dfs(position[0], position[1], map1, &count1);
    // DFS for second person
    dfs(position[2], position[3], map2, &count2);
    // 统计共同可达的聚餐地点
    int okSum =0;
    for(int i=0;i<count1;i++){
        for(int j=0;j<count2;j++){
            if(isSame(map1[i][0], map1[i][1], map2[j][0], map2[j][1])){
                okSum++;
                break;
            }
        }
    }
    printf("%d\n", okSum);
    return 0;
}
**

九、C++算法源码

// C++实现

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, n;
    cin >> m >> n;
    vector<vector<int>> arr(m, vector<int>(n));
    vector<pair<int, int>> positions;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin >> arr[i][j];
            if(arr[i][j] == 2){
                positions.emplace_back(i, j);
            }
        }
    }
    // 定义四个方向
    int arrX[4] = {-1, 0, 1, 0};
    int arrY[4] = {0, 1, 0, -1};
    // 存储可达的聚餐地点
    unordered_set<string> map1, map2;

    // DFS函数
    function<void(int, int, unordered_set<string>&)> dfs = [&](int x, int y, unordered_set<string> &map_reach) {
        if(arr[x][y] == 3){
            string key = to_string(x) + "@" + to_string(y);
            map_reach.insert(key);
            return;
        }
        int temp = arr[x][y];
        arr[x][y] = -1; // 标记为已访问
        for(int i=0;i<4;i++){
            int a = x + arrX[i];
            int b = y + arrY[i];
            if(a >=0 && a < m && b >=0 && b < n && arr[a][b] !=1 && arr[a][b]!=-1){
                dfs(a, b, map_reach);
            }
        }
        arr[x][y] = temp; // 恢复原值
    };

    // 对两个人分别进行DFS
    dfs(positions[0].first, positions[0].second, map1);
    dfs(positions[1].first, positions[1].second, map2);

    // 统计共同可达的聚餐地点
    int okSum =0;
    for(auto &key: map1){
        if(map2.find(key) != map2.end()){
            okSum++;
        }
    }
    cout << okSum;
    return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2025 B卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

在这里插入图片描述

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

哪 吒

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值