华为OD机试 - 上班之路/是否能到达公司 - 广度优先搜索bfs（Python/JS/C/C++ 2025 B卷 100分）

于 2025-05-19 10:15:47 发布
阅读量468 收藏 9
点赞数 25
分类专栏： 搬砖工逆袭Java架构师 文章标签： 华为od 宽度优先 python 华为OD机试 2025B卷
本文为博主原创文章，未经博主允许不得转载。
本文链接：https://blog.csdn.net/guorui_java/article/details/148057077
版权

在这里插入图片描述

2025B卷华为OD机试统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

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

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

一、题目描述

Jungle 生活在美丽的蓝鲸城，大马路都是方方正正，但是每天马路的封闭情况都不一样。
地图由以下元素组成：

.：空地，可以达到；

*：路障，不可达到；

S：Jungle 的家；

T：公司；

其中我们会限制 Jungle 拐弯的次数，同时 Jungle 可以清除给定个数的路障，现在你的任务是计算 Jungle 是否可以从家里出发到达公司。

二、输入描述

输入的第一行为两个整数 t, c（0 ≤ t, c ≤ 100），t 代表可以拐弯的次数，c 代表可以清除的路障个数。

输入的第二行为两个整数 n, m（1 ≤ n, m ≤ 100），代表地图的大小。

接下来是 n 行包含 m 个字符的地图。n 和 m 可能不一样大。

我们保证地图里有 S 和 T。

三、输出描述

输出是否可以从家里出发到达公司，是则输出 YES，不能则输出 NO。

四、测试用例

测试用例1：

1、输入

2 0
5 5
…S…
****.
T…
****.
…

2、输出

YES

测试用例2：

1、输入

1 2
5 5
.S.

…*…

T…

2、输出

NO

五、解题思路

使用广度优先搜索(BFS)算法，将问题建模为状态空间搜索。每个状态包含位置、方向、拐弯次数和清障次数，通过队列存储待搜索状态，用集合记录已访问状态来避免重复。

数据结构和算法选择原因

BFS: 能系统地探索所有可能路径，保证找到解

队列: 实现BFS的先进先出特性

哈希集合: 快速查找和插入已访问状态，避免重复搜索

状态编码: 将多维状态压缩为字符串或数值，便于存储和比较

六、Python算法源码

# Python版本 - 限制拐弯和清障的路径搜索
from collections import deque

def bfs(map_grid, n, m, start_x, start_y, end_x, end_y, max_turns, max_clear):
    """
    使用BFS搜索路径，考虑拐弯次数和清障能力
    Args:
        map_grid: 地图
        n: 地图行数  
        m: 地图列数
        start_x: 起点行坐标
        start_y: 起点列坐标
        end_x: 终点行坐标
        end_y: 终点列坐标
        max_turns: 最大拐弯次数
        max_clear: 最大清障次数
    Returns:
        是否能到达终点
    """
    # 定义方向数组：上、右、下、左
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    # 队列存储状态：[x坐标, y坐标, 方向, 拐弯次数, 已清除路障数]
    queue = deque()
    
    # 访问状态集合
    visited = set()
    
    # 初始化：从四个方向开始搜索
    for direction in range(4):
        state = (start_x, start_y, direction, 0, 0)
        queue.append(state)
        visited.add(state)
    
    while queue:
        # 取出当前状态
        x, y, direction, turns, cleared = queue.popleft()
        
        # 到达终点
        if x == end_x and y == end_y:
            return True
        
        # 向当前方向前进
        new_x = x + dx[direction]
        new_y = y + dy[direction]
        
        # 检查边界
        if 0 <= new_x < n and 0 <= new_y < m:
            new_cleared = cleared
            
            # 如果是路障，需要清除
            if map_grid[new_x][new_y] == '*':
                new_cleared += 1
                if new_cleared > max_clear:
                    continue  # 超过清障限制，跳过
            
            state = (new_x, new_y, direction, turns, new_cleared)
            if state not in visited:
                visited.add(state)
                queue.append(state)
        
        # 拐弯：尝试其他三个方向
        if turns < max_turns:
            for new_dir in range(4):
                if new_dir != direction:  # 不同于当前方向才是拐弯
                    next_x = x + dx[new_dir]
                    next_y = y + dy[new_dir]
                    
                    # 检查边界
                    if 0 <= next_x < n and 0 <= next_y < m:
                        new_cleared = cleared
                        
                        # 如果是路障，需要清除
                        if map_grid[next_x][next_y] == '*':
                            new_cleared += 1
                            if new_cleared > max_clear:
                                continue  # 超过清障限制，跳过
                        
                        state = (next_x, next_y, new_dir, turns + 1, new_cleared)
                        if state not in visited:
                            visited.add(state)
                            queue.append(state)
    
    return False  # 无法到达终点


def main():
    # 读取拐弯次数限制t和可清除路障数c
    t, c = map(int, input().split())
    
    # 读取地图大小
    n, m = map(int, input().split())
    
    # 读取地图并找到起点和终点
    map_grid = []
    start_x = start_y = end_x = end_y = -1
    
    for i in range(n):
        line = input().strip()
        map_grid.append(line)
        for j in range(m):
            if line[j] == 'S':
                start_x, start_y = i, j
            elif line[j] == 'T':
                end_x, end_y = i, j
    
    # 使用BFS搜索路径
    can_reach = bfs(map_grid, n, m, start_x, start_y, end_x, end_y, t, c)
    
    # 输出结果
    print("YES" if can_reach else "NO")


if __name__ == "__main__":
    main()

七、JavaScript算法源码

/**
 * 使用BFS搜索路径，考虑拐弯次数和清障能力
 * @param {Array} mapGrid - 地图二维数组
 * @param {number} n - 地图行数
 * @param {number} m - 地图列数  
 * @param {number} startX - 起点行坐标
 * @param {number} startY - 起点列坐标
 * @param {number} endX - 终点行坐标
 * @param {number} endY - 终点列坐标
 * @param {number} maxTurns - 最大拐弯次数
 * @param {number} maxClear - 最大清障次数
 * @returns {boolean} 是否能到达终点
 */
function bfs(mapGrid, n, m, startX, startY, endX, endY, maxTurns, maxClear) {
    // 定义方向数组：上、右、下、左
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    
    // 队列存储状态：[x坐标, y坐标, 方向, 拐弯次数, 已清除路障数]
    const queue = [];
    
    // 访问状态集合
    const visited = new Set();
    
    // 初始化：从四个方向开始搜索
    for (let direction = 0; direction < 4; direction++) {
        const state = `${startX},${startY},${direction},0,0`;
        queue.push([startX, startY, direction, 0, 0]);
        visited.add(state);
    }
    
    while (queue.length > 0) {
        // 取出当前状态
        const [x, y, direction, turns, cleared] = queue.shift();
        
        // 到达终点
        if (x === endX && y === endY) {
            return true;
        }
        
        // 向当前方向前进
        const newX = x + dx[direction];
        const newY = y + dy[direction];
        
        // 检查边界
        if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
            let newCleared = cleared;
            
            // 如果是路障，需要清除
            if (mapGrid[newX][newY] === '*') {
                newCleared++;
                if (newCleared > maxClear) {
                    continue; // 超过清障限制，跳过
                }
            }
            
            const state = `${newX},${newY},${direction},${turns},${newCleared}`;
            if (!visited.has(state)) {
                visited.add(state);
                queue.push([newX, newY, direction, turns, newCleared]);
            }
        }
        
        // 拐弯：尝试其他三个方向
        if (turns < maxTurns) {
            for (let newDir = 0; newDir < 4; newDir++) {
                if (newDir !== direction) { // 不同于当前方向才是拐弯
                    const nextX = x + dx[newDir];
                    const nextY = y + dy[newDir];
                    
                    // 检查边界
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                        let newCleared = cleared;
                        
                        // 如果是路障，需要清除
                        if (mapGrid[nextX][nextY] === '*') {
                            newCleared++;
                            if (newCleared > maxClear) {
                                continue; // 超过清障限制，跳过
                            }
                        }
                        
                        const state = `${nextX},${nextY},${newDir},${turns + 1},${newCleared}`;
                        if (!visited.has(state)) {
                            visited.add(state);
                            queue.push([nextX, nextY, newDir, turns + 1, newCleared]);
                        }
                    }
                }
            }
        }
    }
    
    return false; // 无法到达终点
}

// 主函数
function main() {
    // 模拟读取输入（在实际环境中会用readline或其他输入方式）
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });
    
    let lineIndex = 0;
    let t, c, n, m;
    let mapGrid = [];
    let startX = -1, startY = -1, endX = -1, endY = -1;
    
    rl.on('line', (line) => {
        if (lineIndex === 0) {
            // 读取拐弯次数限制t和可清除路障数c
            [t, c] = line.split(' ').map(Number);
        } else if (lineIndex === 1) {
            // 读取地图大小
            [n, m] = line.split(' ').map(Number);
        } else {
            // 读取地图
            const mapLine = line.trim();
            mapGrid.push(mapLine);
            
            // 找到起点和终点
            for (let j = 0; j < mapLine.length; j++) {
                if (mapLine[j] === 'S') {
                    startX = lineIndex - 2;
                    startY = j;
                } else if (mapLine[j] === 'T') {
                    endX = lineIndex - 2;
                    endY = j;
                }
            }
            
            // 当读取完所有地图行时，开始搜索
            if (mapGrid.length === n) {
                // 使用BFS搜索路径
                const canReach = bfs(mapGrid, n, m, startX, startY, endX, endY, t, c);
                
                // 输出结果
                console.log(canReach ? "YES" : "NO");
                rl.close();
            }
        }
        lineIndex++;
    });
}

// 如果是直接运行这个文件，则执行main函数
if (require.main === module) {
    main();
}

八、C算法源码

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

// 定义最大地图大小
#define MAX_SIZE 100
// 定义队列最大大小
#define MAX_QUEUE_SIZE 1000000

// 状态结构体
typedef struct {
    int x, y;        // 坐标
    int direction;   // 方向
    int turns;       // 拐弯次数
    int cleared;     // 已清除路障数
} State;

// 队列结构体
typedef struct {
    State states[MAX_QUEUE_SIZE];  // 状态数组
    int front, rear;               // 队首队尾指针
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

// 判断队列是否为空
bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

// 入队
void enqueue(Queue* q, State state) {
    q->states[q->rear] = state;
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}

// 出队
State dequeue(Queue* q) {
    State state = q->states[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return state;
}

/**
 * 使用BFS搜索路径，考虑拐弯次数和清障能力
 * @param map 地图二维字符数组
 * @param n 地图行数
 * @param m 地图列数
 * @param startX 起点行坐标
 * @param startY 起点列坐标
 * @param endX 终点行坐标
 * @param endY 终点列坐标
 * @param maxTurns 最大拐弯次数
 * @param maxClear 最大清障次数
 * @return 是否能到达终点
 */
bool bfs(char map[MAX_SIZE][MAX_SIZE], int n, int m, int startX, int startY, 
         int endX, int endY, int maxTurns, int maxClear) {
    // 定义方向数组：上、右、下、左
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    
    // 访问状态数组：visited[x][y][direction][turns][cleared]
    // 为了节省内存，使用五维数组标记是否访问过
    static bool visited[MAX_SIZE][MAX_SIZE][4][101][101];
    memset(visited, false, sizeof(visited));
    
    // 初始化队列
    Queue queue;
    initQueue(&queue);
    
    // 初始化：从四个方向开始搜索
    for (int direction = 0; direction < 4; direction++) {
        State initialState = {startX, startY, direction, 0, 0};
        enqueue(&queue, initialState);
        visited[startX][startY][direction][0][0] = true;
    }
    
    while (!isEmpty(&queue)) {
        // 取出当前状态
        State curr = dequeue(&queue);
        int x = curr.x;
        int y = curr.y;
        int direction = curr.direction;
        int turns = curr.turns;
        int cleared = curr.cleared;
        
        // 到达终点
        if (x == endX && y == endY) {
            return true;
        }
        
        // 向当前方向前进
        int newX = x + dx[direction];
        int newY = y + dy[direction];
        
        // 检查边界
        if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
            int newCleared = cleared;
            
            // 如果是路障，需要清除
            if (map[newX][newY] == '*') {
                newCleared++;
                if (newCleared > maxClear) {
                    continue; // 超过清障限制，跳过
                }
            }
            
            // 检查是否已访问过这个状态
            if (!visited[newX][newY][direction][turns][newCleared]) {
                visited[newX][newY][direction][turns][newCleared] = true;
                State newState = {newX, newY, direction, turns, newCleared};
                enqueue(&queue, newState);
            }
        }
        
        // 拐弯：尝试其他三个方向
        if (turns < maxTurns) {
            for (int newDir = 0; newDir < 4; newDir++) {
                if (newDir != direction) { // 不同于当前方向才是拐弯
                    int nextX = x + dx[newDir];
                    int nextY = y + dy[newDir];
                    
                    // 检查边界
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                        int newCleared = cleared;
                        
                        // 如果是路障，需要清除
                        if (map[nextX][nextY] == '*') {
                            newCleared++;
                            if (newCleared > maxClear) {
                                continue; // 超过清障限制，跳过
                            }
                        }
                        
                        // 检查是否已访问过这个状态
                        if (!visited[nextX][nextY][newDir][turns + 1][newCleared]) {
                            visited[nextX][nextY][newDir][turns + 1][newCleared] = true;
                            State newState = {nextX, nextY, newDir, turns + 1, newCleared};
                            enqueue(&queue, newState);
                        }
                    }
                }
            }
        }
    }
    
    return false; // 无法到达终点
}

int main() {
    int t, c; // 拐弯次数限制和可清除路障数
    int n, m; // 地图大小
    char map[MAX_SIZE][MAX_SIZE]; // 地图
    int startX = -1, startY = -1; // 起点坐标
    int endX = -1, endY = -1;     // 终点坐标
    
    // 读取拐弯次数限制t和可清除路障数c
    scanf("%d %d", &t, &c);
    
    // 读取地图大小
    scanf("%d %d", &n, &m);
    
    // 读取地图并找到起点和终点
    for (int i = 0; i < n; i++) {
        scanf("%s", map[i]);
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 'S') {
                startX = i;
                startY = j;
            } else if (map[i][j] == 'T') {
                endX = i;
                endY = j;
            }
        }
    }
    
    // 使用BFS搜索路径
    bool canReach = bfs(map, n, m, startX, startY, endX, endY, t, c);
    
    // 输出结果
    printf("%s\n", canReach ? "YES" : "NO");
    
    return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
using namespace std;

// 状态结构体
struct State {
    int x, y;        // 坐标
    int direction;   // 方向
    int turns;       // 拐弯次数
    int cleared;     // 已清除路障数
    
    // 构造函数
    State(int x, int y, int dir, int turns, int cleared) 
        : x(x), y(y), direction(dir), turns(turns), cleared(cleared) {}
};

/**
 * 使用BFS搜索路径，考虑拐弯次数和清障能力
 * @param mapGrid 地图二维字符向量
 * @param n 地图行数
 * @param m 地图列数
 * @param startX 起点行坐标
 * @param startY 起点列坐标
 * @param endX 终点行坐标
 * @param endY 终点列坐标
 * @param maxTurns 最大拐弯次数
 * @param maxClear 最大清障次数
 * @return 是否能到达终点
 */
bool bfs(const vector<string>& mapGrid, int n, int m, int startX, int startY, 
         int endX, int endY, int maxTurns, int maxClear) {
    // 定义方向数组：上、右、下、左
    vector<int> dx = {-1, 0, 1, 0};
    vector<int> dy = {0, 1, 0, -1};
    
    // 队列存储状态
    queue<State> q;
    
    // 访问状态集合，使用字符串作为状态标识
    set<string> visited;
    
    // 初始化：从四个方向开始搜索
    for (int direction = 0; direction < 4; direction++) {
        q.push(State(startX, startY, direction, 0, 0));
        // 构建状态标识符：x,y,direction,turns,cleared
        string stateKey = to_string(startX) + "," + to_string(startY) + "," + 
                         to_string(direction) + "," + to_string(0) + "," + to_string(0);
        visited.insert(stateKey);
    }
    
    while (!q.empty()) {
        // 取出当前状态
        State curr = q.front();
        q.pop();
        
        int x = curr.x;
        int y = curr.y;
        int direction = curr.direction;
        int turns = curr.turns;
        int cleared = curr.cleared;
        
        // 到达终点
        if (x == endX && y == endY) {
            return true;
        }
        
        // 向当前方向前进
        int newX = x + dx[direction];
        int newY = y + dy[direction];
        
        // 检查边界
        if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
            int newCleared = cleared;
            
            // 如果是路障，需要清除
            if (mapGrid[newX][newY] == '*') {
                newCleared++;
                if (newCleared > maxClear) {
                    continue; // 超过清障限制，跳过
                }
            }
            
            // 构建状态标识符
            string stateKey = to_string(newX) + "," + to_string(newY) + "," + 
                             to_string(direction) + "," + to_string(turns) + "," + to_string(newCleared);
            
            // 检查是否已访问过这个状态
            if (visited.find(stateKey) == visited.end()) {
                visited.insert(stateKey);
                q.push(State(newX, newY, direction, turns, newCleared));
            }
        }
        
        // 拐弯：尝试其他三个方向
        if (turns < maxTurns) {
            for (int newDir = 0; newDir < 4; newDir++) {
                if (newDir != direction) { // 不同于当前方向才是拐弯
                    int nextX = x + dx[newDir];
                    int nextY = y + dy[newDir];
                    
                    // 检查边界
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                        int newCleared = cleared;
                        
                        // 如果是路障，需要清除
                        if (mapGrid[nextX][nextY] == '*') {
                            newCleared++;
                            if (newCleared > maxClear) {
                                continue; // 超过清障限制，跳过
                            }
                        }
                        
                        // 构建状态标识符
                        string stateKey = to_string(nextX) + "," + to_string(nextY) + "," + 
                                         to_string(newDir) + "," + to_string(turns + 1) + "," + to_string(newCleared);
                        
                        // 检查是否已访问过这个状态
                        if (visited.find(stateKey) == visited.end()) {
                            visited.insert(stateKey);
                            q.push(State(nextX, nextY, newDir, turns + 1, newCleared));
                        }
                    }
                }
            }
        }
    }
    
    return false; // 无法到达终点
}

int main() {
    int t, c; // 拐弯次数限制和可清除路障数
    int n, m; // 地图大小
    vector<string> mapGrid; // 地图
    int startX = -1, startY = -1; // 起点坐标
    int endX = -1, endY = -1;     // 终点坐标
    
    // 读取拐弯次数限制t和可清除路障数c
    cin >> t >> c;
    
    // 读取地图大小
    cin >> n >> m;
    
    // 读取地图并找到起点和终点
    for (int i = 0; i < n; i++) {
        string line;
        cin >> line;
        mapGrid.push_back(line);
        
        // 找到起点和终点
        for (int j = 0; j < m; j++) {
            if (line[j] == 'S') {
                startX = i;
                startY = j;
            } else if (line[j] == 'T') {
                endX = i;
                endY = j;
            }
        }
    }
    
    // 使用BFS搜索路径
    bool canReach = bfs(mapGrid, n, m, startX, startY, endX, endY, t, c);
    
    // 输出结果
    cout << (canReach ? "YES" : "NO") << endl;
    
    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、付费专栏及课程。

余额充值