华为OD机试 - 自动泊车- 广度优先搜索BFS（Python/JS/C/C++ 新系统 200分）

华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述在某商场的地下停车场部署了一套智能导航系统。停车场可以看作是一个 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。四、测试用例测试用例11、输入1 13 30 0 00 0 00 0 02、输出23、说明从 [0,0] 到 [1,1] 最短路径有很多种例如[0,0] - [0,1] - [1,1][0,0] - [1,0] - [1,1]最短步数都是 2。测试用例21、输入2 23 30 1 00 1 00 0 02、输出43、说明中间一列部分被障碍物挡住只能绕路[0,0] - [1,0] - [2,0] - [2,1] - [2,2]共 4 步。五、解题思路1、题意分析停车场是一个 row * col 的网格0可通行1不可通行起点固定为 [0,0]终点为 [m,n]每次只能上下左右移动一格求最少步数这就是一个标准的网格最短路径问题。2、为什么用 BFS因为每移动一格的代价都相同都是 1要求的是最短路径步数对于这种“边权相同”的最短路问题BFS 是最优选择BFS 从起点一层一层向外扩展第一次到达目标点时走过的步数一定是最短的。3、具体步骤读入目标位置、地图大小和网格数据如果目标位置本身是障碍物直接输出 -1从起点 [0,0] 开始做 BFS每次从队列中取出一个位置向四个方向扩展遇到合法且未访问且可通行的位置就加入队列如果到达目标位置立即输出当前步数如果队列空了还没到达说明无法到达输出 -1六、Python算法源码fromcollectionsimportdequeimportsysdefmain():# 读取所有输入并按空白字符分割datasys.stdin.read().strip().split()# 如果没有输入直接结束ifnotdata:returnititer(data)# 读取目标车位坐标mint(next(it))nint(next(it))# 读取停车场行列数rowint(next(it))colint(next(it))# 读取网格grid[[int(next(it))for_inrange(col)]for_inrange(row)]# 如果目标位置是障碍物则无法到达ifgrid[m][n]1:print(-1)return# visited 用于标记某个位置是否已经访问过visited[[False]*colfor_inrange(row)]# BFS 队列中保存 (x, y, step)queuedeque()queue.append((0,0,0))visited[0][0]True# 四个方向下、上、右、左dirs[(1,0),(-1,0),(0,1),(0,-1)]# 开始 BFSwhilequeue:x,y,stepqueue.popleft()# 如果到达目标位置输出步数ifxmandyn:print(step)return# 尝试往四个方向走fordx,dyindirs:nxxdx nyydy# 判断是否越界、是否访问过、是否可通行if0nxrowand0nycolandnotvisited[nx][ny]andgrid[nx][ny]0:visited[nx][ny]Truequeue.append((nx,ny,step1))# 队列为空仍未到达目标print(-1)if__name____main__:main()七、JavaScript算法源码constfsrequire(fs);// 读取标准输入constinputfs.readFileSync(0,utf8).trim();if(input.length0){// 按空白字符分割并转为数字constarrinput.split(/\s/).map(Number);letidx0;// 读取目标位置constmarr[idx];constnarr[idx];// 读取停车场行列数constrowarr[idx];constcolarr[idx];// 读取网格constgridArray.from({length:row},()Array(col).fill(0));for(leti0;irow;i){for(letj0;jcol;j){grid[i][j]arr[idx];}}// 如果目标位置本身就是障碍物直接输出 -1if(grid[m][n]1){console.log(-1);}else{// visited 数组用于标记访问状态constvisitedArray.from({length:row},()Array(col).fill(false));// 使用数组模拟队列head 指向队头constqueue[];lethead0;// 起点入队queue.push([0,0,0]);visited[0][0]true;// 四个方向constdirs[[1,0],[-1,0],[0,1],[0,-1]];letans-1;// BFSwhile(headqueue.length){const[x,y,step]queue[head];// 找到目标位置if(xmyn){ansstep;break;}// 四方向扩展for(const[dx,dy]ofdirs){constnxxdx;constnyydy;if(nx0nxrowny0nycol!visited[nx][ny]grid[nx][ny]0){visited[nx][ny]true;queue.push([nx,ny,step1]);}}}console.log(ans);}}八、C算法源码#includestdio.h#includestdlib.h/* 定义队列中节点的结构体 */typedefstruct{intx;// 当前所在行inty;// 当前所在列intstep;// 从起点走到当前点的步数}Node;intmain(){intm,n,row,col;/* 读取目标车位坐标 */if(scanf(%d %d,m,n)!2){return0;}/* 读取停车场的行数和列数 */scanf(%d %d,row,col);/* 动态申请二维数组 grid 和 visited */int**grid(int**)malloc(row*sizeof(int*));int**visited(int**)malloc(row*sizeof(int*));for(inti0;irow;i){grid[i](int*)malloc(col*sizeof(int));visited[i](int*)calloc(col,sizeof(int));for(intj0;jcol;j){scanf(%d,grid[i][j]);}}/* 如果目标位置是障碍物则直接输出 -1 */if(grid[m][n]1){printf(-1\n);for(inti0;irow;i){free(grid[i]);free(visited[i]);}free(grid);free(visited);return0;}/* 队列最多存放 row * col 个节点 */Node*queue(Node*)malloc(row*col*sizeof(Node));inthead0,tail0;/* 起点入队 */queue[tail](Node){0,0,0};visited[0][0]1;/* 四个方向下、上、右、左 */intdirs[4][2]{{1,0},{-1,0},{0,1},{0,-1}};/* BFS */while(headtail){Node curqueue[head];/* 如果到达目标点输出结果 */if(cur.xmcur.yn){printf(%d\n,cur.step);for(inti0;irow;i){free(grid[i]);free(visited[i]);}free(grid);free(visited);free(queue);return0;}/* 四个方向扩展 */for(inti0;i4;i){intnxcur.xdirs[i][0];intnycur.ydirs[i][1];/* 判断是否越界、是否访问过、是否可通行 */if(nx0nxrowny0nycol!visited[nx][ny]grid[nx][ny]0){visited[nx][ny]1;queue[tail](Node){nx,ny,cur.step1};}}}/* 无法到达目标位置 */printf(-1\n);for(inti0;irow;i){free(grid[i]);free(visited[i]);}free(grid);free(visited);free(queue);return0;}九、C算法源码#includeiostream#includevector#includequeueusingnamespacestd;/* 定义 BFS 队列中的节点结构 */structNode{intx;// 当前行inty;// 当前列intstep;// 从起点走到当前节点的步数};intmain(){intm,n,row,col;// 读取目标车位坐标if(!(cinmn)){return0;}// 读取停车场行列数cinrowcol;// 读取网格vectorvectorintgrid(row,vectorint(col));for(inti0;irow;i){for(intj0;jcol;j){cingrid[i][j];}}// 如果目标点本身是障碍物直接输出 -1if(grid[m][n]1){cout-1endl;return0;}// visited[i][j] 表示该位置是否访问过vectorvectorintvisited(row,vectorint(col,0));// BFS 队列queueNodeq;q.push({0,0,0});visited[0][0]1;// 四个方向下、上、右、左intdirs[4][2]{{1,0},{-1,0},{0,1},{0,-1}};// BFSwhile(!q.empty()){Node curq.front();q.pop();// 到达目标点输出最短步数if(cur.xmcur.yn){coutcur.stependl;return0;}// 向四个方向尝试扩展for(autodir:dirs){intnxcur.xdir[0];intnycur.ydir[1];// 判断是否合法if(nx0nxrowny0nycol!visited[nx][ny]grid[nx][ny]0){visited[nx][ny]1;q.push({nx,ny,cur.step1});}}}// 无法到达cout-1endl;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。