智能驾驶问题

一、题目描述有一辆汽车需要从 m*n 的地图的左上角(起点)开往地图的右下角(终点)去往每一个地区都需要消耗一定的油量加油站可进行加油。请你计算汽车确保从起点到达终点时所需的最少初始油量说明:(1) 智能汽车可以上下左右四个方向移动1(2) 地图上的数字取值是 0或-1 或者正整数:1: 表示加油站可以加满油汽车的油箱容量最大为 100;0: 表示这个地区是障碍物汽车不能通过正整数: 表示汽车走过这个地区的耗油量(3) 如果汽车无论如何都无法到达终点则返回 -1。二、输入输出描述输入描述第一行两个数字MN表示地图的大小为 M,N(0 M,N 200)接下来 M 行每行 N 个数字0 /-1 / 正整数输出描述如果汽车可以到达终点则返回最少的初始油量如果汽车无论如何都无法到达终点则返回-1三、示例输入2,210,2030,40输出70说明输入4,410,30,30,2030,30,-1,100,20,20,4010,-1,30,40输出70说明输入4,410,30,30,2030,30,20,1010,20,10,4010,20,30,40输出-1说明四、解题思路1. 核心思想从小到大枚举初始油量 BFS 状态搜索从 0 到 100从小到大尝试每一个初始油量对每个初始油量用BFS走地图判断能否到达终点第一个能成功的初始油量就是最小答案2. 问题本质分析这是一个带油量状态的最短路径 / 可达性问题约束油量 ≥ 0油箱上限 100遇到加油站直接加满目标找到最小的初始油量让小车能从起点走到终点状态必须记录(x, y, 当前油量)三个信息避免重复走3. 核心逻辑从小到大枚举初始油量保证找到的第一个就是最小值BFS 搜索路径每个状态记录坐标 剩余油量障碍物不能走普通格子扣油加油站加满油量不能为负三维去重vis[x][y][oil]避免重复搜索相同状态一旦找到能到达终点的初始油量直接输出4. 步骤拆解输入读取读取地图行列与网格数据从小到大枚举初始油量从 0 到 100 依次尝试BFS 判断可达性初始化队列与状态标记处理起点格子障碍 / 加油 / 扣油四方向扩展处理格子规则到达终点返回成功输出结果第一个成功的初始油量 最小答案都失败输出 -1。五、代码实现import java.util.*; public class Main { static int M, N; static int[][] map; static int[] dx {-1, 1, 0, 0}; static int[] dy {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc new Scanner(System.in); M sc.nextInt(); N sc.nextInt(); map new int[M][N]; for (int i 0; i M; i) { for (int j 0; j N; j) { map[i][j] sc.nextInt(); } } // 油箱最大100从小到大尝试初始油量 for (int start 0; start 100; start) { if (bfs(start)) { System.out.println(start); return; } } System.out.println(-1); } // BFS给定初始油量能否到达终点 static boolean bfs(int startOil) { boolean[][][] vis new boolean[M][N][101]; Queueint[] q new LinkedList(); // 起点格子也要扣油 或 加油 int first map[0][0]; int cur; if (first 0) return false; // 障碍 if (first -1) cur 100; // 加油站 else { cur startOil - first; if (cur 0) return false; } q.add(new int[]{0, 0, cur}); vis[0][0][cur] true; while (!q.isEmpty()) { int[] now q.poll(); int x now[0]; int y now[1]; int oil now[2]; // 到达终点 if (x M - 1 y N - 1) { return true; } for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx M || ny 0 || ny N) continue; int val map[nx][ny]; if (val 0) continue; // 障碍物 int newOil; if (val -1) { newOil 100; // 加满 } else { newOil oil - val; if (newOil 0) continue; } if (!vis[nx][ny][newOil]) { vis[nx][ny][newOil] true; q.add(new int[]{nx, ny, newOil}); } } } return false; } }