华为OD 2026机试真题 Java&Go 语言实现【自动泊车】

一、题目

题目描述：

在某商场的地下停车场，部署了一套智能导航系统。停车场可以看作是一个 r × c 的网格矩阵，其中：

• 0 表示该位置是空的行车道，车辆可以通行。
• 1 表示该位置存有障碍物、立柱或其他已停放的车辆，车辆无法通行。

停车场的入口统一设在坐标 [0, 0] 处。现在有一辆车进入停车场，需要前往指定的目标车位 [m, n]。

车辆在停车场内只能沿着上、下、左、右四个方向移动，每移动一个格子计为步数 1。请你帮车主规划一条从入口到目标车位的最短路径。

📥 输入描述

⚠️ 约束条件

• 1 < row, col < 200
• 0 < m < row, 0 < n < col
• 入口 [0, 0] 保证为空位（即值为 0）

📤 输出描述

• 输出一个整数，表示从入口 [0, 0] 到目标车位 [m, n] 的最短路径步数。
• 如果由于障碍物阻挡无法到达目标位置，则输出 -1。

🧪 示例 1

输入：

1 1
3 3
0 0 0
0 0 0
0 0 0

输出：2

说明：

停车场大小为 3×3，目标位置在 [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（广度优先搜索） 的应用。题目要求在 r×c 的网格中，从起点 [0, 0] 到终点 [m, n]，只能上下左右移动，避开障碍物（值为1），求最少步数；若不可达则返回 -1。

二、解题思路

🎯 核心思想：BFS（广度优先搜索）

• BFS 天然适合求“无权图”的最短路径。
• 每次扩展一层邻居节点，第一次到达目标点时的步数即为最小步数。
• 使用队列存储待访问的坐标 (row, col) 和当前步数。
• 使用 visited 数组或原地标记避免重复访问。

🧭 步骤分解：

三、Code实现

1、Java✅

import java.util.*;

public class ParkingNavigation {
public static int shortestPath(int m, int n, int row, int col, int[][] grid) {
// 目标位置是障碍物，直接返回 -1
if (grid[m][n] == 1) return -1;

// 方向数组：上、下、左、右
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};

// visited 数组记录是否访问过
boolean[][] visited = new boolean[row][col];
Queue<int[]> queue = new LinkedList<>();

// 起始点 [0,0] 入队，步数为 0
queue.offer(new int[]{0, 0, 0});
visited[0][0] = true;

while (!queue.isEmpty()) {
int[] curr = queue.poll();
int r = curr[0], c = curr[1], steps = curr[2];

// 到达目标
if (r == m && c == n) {
return steps;
}

// 探索四个方向
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];

// 检查边界、障碍物、是否访问过
if (nr >= 0 && nr < row && nc >= 0 && nc < col
&& grid[nr][nc] == 0 && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc, steps + 1});
}
}
}

// 无法到达
return -1;
}

// 测试主函数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int m = sc.nextInt();
int n = sc.nextInt();
int row = sc.nextInt();
int col = sc.nextInt();

int[][] grid = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
grid[i][j] = sc.nextInt();
}
}

System.out.println(shortestPath(m, n, row, col, grid));
}
}

2、Go✅

package main

import (
"bufio"
"fmt"
"os"
)

func shortestPath(m, n, row, col int, grid [][]int) int {
// 目标位置是障碍物，直接返回 -1
if grid[m][n] == 1 {
return -1
}

// 方向数组：上、下、左、右
dr := []int{-1, 1, 0, 0}
dc := []int{0, 0, -1, 1}

// visited 数组
visited := make([][]bool, row)
for i := range visited {
visited[i] = make([]bool, col)
}

// 队列：每个元素是 [r, c, steps]
queue := [][]int{{0, 0, 0}}
visited[0][0] = true

for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
r, c, steps := curr[0], curr[1], curr[2]

// 到达目标
if r == m && c == n {
return steps
}

// 探索四个方向
for i := 0; i < 4; i++ {
nr := r + dr[i]
nc := c + dc[i]

// 检查边界、障碍物、是否访问过
if nr >= 0 && nr < row && nc >= 0 && nc < col &&
grid[nr][nc] == 0 && !visited[nr][nc] {
visited[nr][nc] = true
queue = append(queue, []int{nr, nc, steps + 1})
}
}
}

// 无法到达
return -1
}

func main() {
scanner := bufio.NewScanner(os.Stdin)

var m, n, row, col int
fmt.Scan(&m, &n)
fmt.Scan(&row, &col)

grid := make([][]int, row)
for i := 0; i < row; i++ {
grid[i] = make([]int, col)
for j := 0; j < col; j++ {
fmt.Scan(&grid[i][j])
}
}

result := shortestPath(m, n, row, col, grid)
fmt.Println(result)
}

四、复杂度分析

🎯 总结一句话

“本题是标准 BFS 应用题，关键是正确建模网格、控制边界、避免重复访问，首次抵达目标即得最短路径。”

祝你面试顺利，代码一遍 AC！🚀