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

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述在某商场的地下停车场部署了一套智能导航系统。停车场可以看作是一个 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六、Java算法源码publicclassOdTest{publicstaticvoidmain(String[]args){// 使用 Scanner 从控制台读取输入ScannerscannernewScanner(System.in);// 读取目标车位坐标 m、nintmscanner.nextInt();intnscanner.nextInt();// 读取停车场行数和列数introwscanner.nextInt();intcolscanner.nextInt();// 定义网格数组用于存储停车场状态int[][]gridnewint[row][col];// 读取停车场地图for(inti0;irow;i){for(intj0;jcol;j){grid[i][j]scanner.nextInt();}}// 如果目标位置本身就是障碍物则不可能到达直接输出 -1if(grid[m][n]1){System.out.println(-1);return;}// visited[i][j] 表示位置 (i, j) 是否已经访问过boolean[][]visitednewboolean[row][col];// 四个方向下、上、右、左int[][]dirs{{1,0},{-1,0},{0,1},{0,-1}};// 使用队列进行 BFS// 队列中每个元素是一个长度为 3 的数组// [当前行坐标, 当前列坐标, 从起点走到这里的步数]Queueint[]queuenewArrayDeque();// 起点 [0,0] 入队初始步数为 0queue.offer(newint[]{0,0,0});visited[0][0]true;// 开始 BFSwhile(!queue.isEmpty()){// 取出当前节点int[]curqueue.poll();intxcur[0];intycur[1];intstepcur[2];// 如果当前节点就是目标位置直接输出步数并结束if(xmyn){System.out.println(step);return;}// 向四个方向扩展for(int[]dir:dirs){intnxxdir[0];intnyydir[1];// 判断新位置是否合法// 1. 不能越界// 2. 不能访问过// 3. 不能是障碍物if(nx0nxrowny0nycol!visited[nx][ny]grid[nx][ny]0){// 标记已访问防止重复入队visited[nx][ny]true;// 新位置入队步数加 1queue.offer(newint[]{nx,ny,step1});}}}// 如果 BFS 结束仍未找到目标位置说明无法到达System.out.println(-1);}}七、效果展示1、输入3 45 50 0 1 0 01 0 1 0 10 0 0 0 00 1 1 1 00 0 0 0 02、输出73、说明需要先往下绕到第三行再向右到终点最短步数为 7。下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。