华为OD机试双机位C卷 - 自动泊车 (C++ Python JAVA JS GO)-洪萨配资

自动泊车

2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

考友回忆版:有一个停车场，停车场入口位置[0,0]为0，你要停的位置为[m,n],停车场位置可能是0或者1，是零的位置车可以通行，是1的位置不可以通行，车在停车场内可以只能往四周移动(上下左右)，要求找出从入口到目标车位的最短路径如果无法到达就返回-1.

输入描述

输入 m n,目标车位位置

输入 row ,col, 停车场大小

接下来输入row行，每行为停车场的位置信息。

输出描述

输出一个整数，如果能到到达目标车位输出最短路径，不能到达输出-1.

用例1

输入

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

输出

题解

思路：BFS,模板题

这道题就是经典BFS模板题，借助BFS的一个特性初次访问到某个位置肯定是最小路径。在进行BFS模拟过程中如果第一次到达m n位置可直接退出，同时可以利用上面那个特性进行剪枝，已经访问过的位置不再入栈。
BFS基本逻辑如下：
- 定义visited，初始化所有位置为-1，表示未访问过。定义队列，初始将{0,0}放入队列。
- 接下来使用队列模拟BFS向四周扩散，每次取出队列队首元素{x,y}向四周扩散得到{newX,newY}按照下面逻辑处理:
  - newX < 0 || newY < 0 || newX >= row || newY >= col: 超过边界异常情况，剪枝
  - grid[newX][newY] == 1: 不可通行位置，剪枝
  - visited[newX][newY] != -1: 以访问过位置，不再次搜索，剪枝。
  - 合法情况, {newX,newY}入队，并更新visisted[newX][newY] = visisted[x][y] + 1
- 如果在BFS中遇到{m,n}可提前退出BFS。
注意:由于这道题的题目大意时小伙伴口诉回忆的，可能有部分地方有差异，但总体思路应该没错，大家到时候可以灵活修改一下。但是总体思路肯定时没有问题的

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<climits> using namespace std; int bfs(vector<vector<int>>& grid, int m, int n, int row, int col) { // 上下左右 int direct[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 异常情况细节处理 if (m < 0 || n < 0 || m >= row || n >= col || grid[0][0] == 1) { return -1; } if (m == 0 && n == 0) { return 0; } // 记录起点到{i,j}的 最短路径 vector<vector<int>> visited(row, vector<int>(col, -1)); queue<pair<int,int>> q; q.push({0, 0}); visited[0][0] = 0; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int newX = x + direct[i][0]; int newY = y + direct[i][1]; // 合法性检验 if (newX < 0 || newY < 0 || newX >= row || newY >= col) { continue; } // 不可通行 if (grid[newX][newY] == 1) { continue; } // bfs特性首次到达的路径长度肯定最小 if (visited[newX][newY] != -1) { continue; } // 入队 q.push({newX, newY}); visited[newX][newY] = visited[x][y] + 1; if (newX == m && newY == n) { return visited[newX][newY]; } } } return visited[m][n] == -1 ? -1 : visited[m][n]; } int main() { int m,n; cin >> m >> n; int row, col; cin >> row >> col; vector<vector<int>> grid(row, vector<int>(col)); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { cin >> grid[i][j]; } } int res = bfs(grid, m, n, row, col); cout << res; return 0; }

JAVA

import java.io.*; import java.util.*; /** * BFS 求从 (0,0) 到 (m,n) 的最短路径 * 0 表示可通行，1 表示障碍 */ public class Main { static int bfs(int[][] grid, int m, int n, int row, int col) { // 上下左右方向 int[][] direct = {{-1,0},{1,0},{0,-1},{0,1}}; // 异常情况处理 if (m < 0 || n < 0 || m >= row || n >= col || grid[0][0] == 1) { return -1; } if (m == 0 && n == 0) { return 0; } // 记录最短路径长度，-1 表示未访问 int[][] visited = new int[row][col]; for (int i = 0; i < row; i++) { Arrays.fill(visited[i], -1); } Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); visited[0][0] = 0; while (!queue.isEmpty()) { int[] cur = queue.poll(); int x = cur[0], y = cur[1]; for (int i = 0; i < 4; i++) { int newX = x + direct[i][0]; int newY = y + direct[i][1]; // 边界检查 if (newX < 0 || newY < 0 || newX >= row || newY >= col) continue; // 障碍 if (grid[newX][newY] == 1) continue; // 已访问 if (visited[newX][newY] != -1) continue; visited[newX][newY] = visited[x][y] + 1; if (newX == m && newY == n) { return visited[newX][newY]; } queue.offer(new int[]{newX, newY}); } } return visited[m][n] == -1 ? -1 : visited[m][n]; } public static void main(String[] args) throws Exception { 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(); } } int res = bfs(grid, m, n, row, col); System.out.print(res); } }

Python

importsysfromcollectionsimportdequedefbfs(grid,m,n,row,col):# 上下左右direct=[(-1,0),(1,0),(0,-1),(0,1)]# 异常情况处理ifm<0orn<0orm>=roworn>=colorgrid[0][0]==1:return-1ifm==0andn==0:return0# visited 记录最短距离，-1 表示未访问visited=[[-1]*colfor_inrange(row)]q=deque()q.append((0,0))visited[0][0]=0whileq:x,y=q.popleft()fordx,dyindirect:nx,ny=x+dx,y+dyifnx<0orny<0ornx>=roworny>=col:continueifgrid[nx][ny]==1:continueifvisited[nx][ny]!=-1:continuevisited[nx][ny]=visited[x][y]+1ifnx==mandny==n:returnvisited[nx][ny]q.append((nx,ny))return-1ifvisited[m][n]==-1elsevisited[m][n]defmain():data=list(map(int,sys.stdin.read().split()))idx=0m,n=data[idx],data[idx+1]idx+=2row,col=data[idx],data[idx+1]idx+=2grid=[]for_inrange(row):grid.append(data[idx:idx+col])idx+=colprint(bfs(grid,m,n,row,col))if__name__=="__main__":main()

JavaScript

/** * 使用 readline 接收 ACM 输入 * BFS 求从 (0,0) 到 (m,n) 的最短路径 * 0 表示可通行，1 表示障碍 */'use strict';constreadline=require('readline');// 创建 readline 接口constrl=readline.createInterface({input:process.stdin,output:process.stdout});constlines=[];rl.on('line',line=>{lines.push(line.trim());});rl.on('close',()=>{// 将所有输入按空白切分为数字constdata=lines.join(' ').split(/\s+/).map(Number);letidx=0;// 目标坐标 (m, n)constm=data[idx++];constn=data[idx++];// 网格行列constrow=data[idx++];constcol=data[idx++];// 读取网格constgrid=[];for(leti=0;i<row;i++){grid.push(data.slice(idx,idx+col));idx+=col;}console.log(bfs(grid,m,n,row,col).toString());});/** * BFS 搜索最短路径 * @param {number[][]} grid 网格 * @param {number} m 目标行 * @param {number} n 目标列 * @param {number} row 行数 * @param {number} col 列数 * @returns {number} 最短路径长度，无法到达返回 -1 */functionbfs(grid,m,n,row,col){// 上下左右四个方向constdirect=[[-1,0],[1,0],[0,-1],[0,1]];// 异常情况处理if(m<0||n<0||m>=row||n>=col||grid[0][0]===1){return-1;}// 起点就是终点if(m===0&&n===0){return0;}// visited 记录从起点到该点的最短距离，-1 表示未访问constvisited=Array.from({length:row},()=>Array(col).fill(-1));// 使用数组模拟队列（head 指针避免 shift O(n)）constqueue=[];lethead=0;// 起点入队queue.push([0,0]);visited[0][0]=0;// BFS 主循环while(head<queue.length){const[x,y]=queue[head++];for(const[dx,dy]ofdirect){constnx=x+dx;constny=y+dy;// 边界检查if(nx<0||ny<0||nx>=row||ny>=col)continue;// 障碍物if(grid[nx][ny]===1)continue;// 已访问if(visited[nx][ny]!==-1)continue;// 更新最短距离visited[nx][ny]=visited[x][y]+1;// 如果到达目标点，直接返回（BFS 首次到达即最短）if(nx===m&&ny===n){returnvisited[nx][ny];}// 入队queue.push([nx,ny]);}}// BFS 结束仍未到达returnvisited[m][n]===-1?-1:visited[m][n];}

Go

packagemainimport("bufio""fmt""os")// 节点结构体，表示网格中的一个点typeNodestruct{x,yint}/** * BFS 求从 (0,0) 到 (m,n) 的最短路径 * 0 表示可通行，1 表示障碍 */funcbfs(grid[][]int,m,n,row,colint)int{// 上下左右四个方向direct:=[][]int{{-1,0},{1,0},{0,-1},{0,1},}// 异常情况处理ifm<0||n<0||m>=row||n>=col||grid[0][0]==1{return-1}// 起点即终点ifm==0&&n==0{return0}// visited 记录从起点到该点的最短距离visited:=make([][]int,row)fori:=0;i<row;i++{visited[i]=make([]int,col)forj:=0;j<col;j++{visited[i][j]=-1}}// 使用切片模拟队列queue:=make([]Node,0)queue=append(queue,Node{0,0})visited[0][0]=0head:=0forhead<len(queue){cur:=queue[head]head++for_,d:=rangedirect{nx:=cur.x+d[0]ny:=cur.y+d[1]// 边界检查ifnx<0||ny<0||nx>=row||ny>=col{continue}// 障碍物ifgrid[nx][ny]==1{continue}// 已访问ifvisited[nx][ny]!=-1{continue}// 更新最短距离visited[nx][ny]=visited[cur.x][cur.y]+1// 到达目标点，直接返回ifnx==m&&ny==n{returnvisited[nx][ny]}// 入队queue=append(queue,Node{nx,ny})}}// BFS 结束后判断是否可达ifvisited[m][n]==-1{return-1}returnvisited[m][n]}funcmain(){in:=bufio.NewReader(os.Stdin)varm,nintvarrow,colint// 读取目标坐标fmt.Fscan(in,&m,&n)// 读取网格大小fmt.Fscan(in,&row,&col)// 读取网格grid:=make([][]int,row)fori:=0;i<row;i++{grid[i]=make([]int,col)forj:=0;j<col;j++{fmt.Fscan(in,&grid[i][j])}}// 输出结果fmt.Print(bfs(grid,m,n,row,col))}