目录
题目
思路
Code
题目
题目描述
在某商场的地下停车场，部署了一套智能导航系统。停车场可以看作是一个 r*c 的网格矩阵，其中：
- 0 表示该位置是空的行车道，车辆可以通行。
- 1 表示该位置存有障碍物、立柱或其他已停放的车辆，车辆无法通行。
停车场的入口统一设在坐标 [0, 0] 处。现在有一辆车进入停车场，需要前往指定的目标车位 [m, n]。
车辆在停车场内只能沿着上、下、左、右四个方向移动，每移动一个格子计为步数 1。请你帮车主规划一条从入口到目标车位的最短路径。
输入描述
- 第一行输入两个整数 m 和 n，表示目标车位的行下标和列下标。
- 第二行输入两个整数 row 和 col，表示停车场的总行数和总列数。
- 接下来的 row 行，每行包含 col 个以空格分隔的整数（0 或 1），表示停车场的状态信息。
约束条件：
- 1 < row, col < 200
- 0 < m < row, 0 < n < col
- 入口 [0, 0] 保证为空位。
输出描述
- 输出一个整数，表示从入口 [0, 0] 到目标车位 [m, n] 的最短路径步数。
- 如果由于障碍物阻挡无法到达目标位置，则输出 -1。
示例 1
输入：
1 1
3 3
0 0 0
0 0 0
0 0 0
输出：
2
说明：
停车场大小为 3x3，目标位置在 [1, 1]。
最短路径序列可为：[0, 0] -> [0, 1] -> [1, 1]，共移动 2 步。
或者：[0, 0] -> [1, 0] -> [1, 1]，共移动 2 步。
示例 2
输入：
2 2
3 3
0 1 0
1 1 0
0 0 0
输出：
-1
说明：
由于入口 [0, 0] 的右边 [0, 1] 和下边 [1, 0] 均为障碍物（1），车辆被困在入口处，无法到达目标位置 [2, 2]，因此输出 -1。
示例 3
输入：
0 2
3 3
0 0 0
1 1 0
0 0 0
输出：
2
说明：
目标位置在 [0, 2]。虽然中间有障碍物，但可以沿着第一行直接向右行驶：[0, 0] -> [0, 1] -> [0, 2]，步数为 2。
思路
- 寻找最短路径的最佳算法是 广度优先搜索 (BFS)。BFS 能够保证最先到达目标点的路径一定是最短的。
- 核心步骤：首先进行合法性校验：首先检查起点 [0, 0] 或目标点 [m, n] 是否为障碍物（1）。如果是，直接返回 -1。
- 初始化：创建一个队列，存放当前探索到的坐标和步数 (x, y, step)。起始放入 (0, 0, 0)。
- 防重访问：创建一个 visited 矩阵（或直接修改原矩阵），记录已经走过的位置，避免死循环。
- 循环搜索：
- 从队列中弹出队首元素。
- 判断是否到达目标点，如果是，返回当前步数。
- 向四个方向（上下左右）扩散，检查新坐标是否在矩阵边界内、是否是通道（0）、且未被访问。
- 满足条件的坐标入队，并标记为已访问。
- 终点不可达：如果队列为空仍未找到目标点，则说明路径不通，返回 -1。
Code
import sys from collections import deque def solve(): # 1. 读取目标位置 m (行), n (列) line1 = sys.stdin.readline().split() m, n = map(int, line1) # 2. 读取停车场大小 row (总行数), col (总列数) line2 = sys.stdin.readline().split() row, col = map(int, line2) # 3. 读取停车场矩阵信息 matrix = [] for _ in range(row): matrix.append(list(map(int, sys.stdin.readline().split()))) # --- 边界条件预检查 --- # 如果终点是障碍物(1)，则无法通达 if matrix[m][n] == 1: print("-1") return # 如果起点就是终点 if m == 0 and n == 0: print("0") return # --- BFS 核心逻辑 --- # 队列中存储元素：(x坐标, y坐标, 当前步数) queue = deque([(0, 0, 0)]) # 使用矩阵记录已访问位置，防止重复访问 visited = [[False for _ in range(col)] for _ in range(row)] visited[0][0] = True # 定义四个移动方向：上、下、左、右 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: curr_r, curr_c, dist = queue.popleft() # 尝试向四个方向移动 for dr, dc in directions: nr, nc = curr_r + dr, curr_c + dc # 检查：坐标是否越界 if 0 <= nr < row and 0 <= nc < col: # 检查：是否是车位(0) 且 未访问过 if matrix[nr][nc] == 0 and not visited[nr][nc]: # 检查：是否到达目标位置 if nr == m and nc == n: print(dist + 1) return # 标记访问并入队 visited[nr][nc] = True queue.append((nr, nc, dist + 1)) # 如果遍历结束仍未到达目标位置 print("-1") if __name__ == "__main__": solve()JS
const fs = require('fs'); function solve() { const input = fs.readFileSync(0, 'utf8').split(/\s+/); let cur = 0; // 1. 读取目标位置 m (行), n (列) const m = parseInt(input[cur++]); const n = parseInt(input[cur++]); // 2. 读取停车场大小 row (总行数), col (总列数) const row = parseInt(input[cur++]); const col = parseInt(input[cur++]); // 3. 读取停车场矩阵信息 const matrix = []; for (let i = 0; i < row; i++) { let r_data = []; for (let j = 0; j < col; j++) { r_data.push(parseInt(input[cur++])); } matrix.push(r_data); } // --- 边界条件预检查 --- // 如果终点是障碍物(1)，则无法通达 if (matrix[m][n] === 1) { console.log("-1"); return; } // 如果起点就是终点 if (m === 0 && n === 0) { console.log("0"); return; } // --- BFS 核心逻辑 --- // 队列中存储元素：(x坐标, y坐标, 当前步数) let queue = [[0, 0, 0]]; // 使用矩阵记录已访问位置，防止重复访问 let visited = Array.from({ length: row }, () => Array(col).fill(false)); visited[0][0] = true; // 定义四个移动方向：上、下、左、右 const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; let head = 0; while (head < queue.length) { let [curr_r, curr_c, dist] = queue[head++]; // 尝试向四个方向移动 for (let [dr, dc] of directions) { let nr = curr_r + dr; let nc = curr_c + dc; // 检查：坐标是否越界 if (nr >= 0 && nr < row && nc >= 0 && nc < col) { // 检查：是否是车位(0) 且 未访问过 if (matrix[nr][nc] === 0 && !visited[nr][nc]) { // 检查：是否到达目标位置 if (nr === m && nc === n) { console.log(dist + 1); return; } // 标记访问并入队 visited[nr][nc] = true; queue.push([nr, nc, dist + 1]); } } } } // 如果遍历结束仍未到达目标位置 console.log("-1"); } solve();【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群：830285880】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
