题目
起火迷宫
解题思路
这是一个典型的多源 BFS 问题，需要同时模拟：
- 火焰的蔓延（从多个 F 出发）；
- 乔（J）的移动。
关键点：
- 火和人同时移动，每单位时间火向四周扩散，人向四个方向走一格；
- 人不能进入已着火或即将着火的格子；
- 一旦到达边界，再花 1 单位时间即可逃脱。
核心策略
使用两个 BFS：
- 先跑火焰的 BFS：从所有
F开始，计算每个空地最早在第几时刻被点燃（记为fireTime[x][y]）； - 再跑乔的 BFS：从
J开始，每一步只走到未被点燃且安全的格子；- 安全条件：到达新格子的时间
t+1必须 严格小于 该格子被点燃的时间（即t+1 < fireTime[nx][ny]）； - 若某步能走到边界，则总时间为当前时间 + 1（额外耗时）；
- 若无法到达边界，输出
IMPOSSIBLE。
- 安全条件：到达新格子的时间
✅ 注意：火的蔓延是“同步”的，即同一时间火会向所有相邻空地传播。
参考代码（Java）
import java.util.*;
public class Main {
// 四个方向：右、左、下、上
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int R = sc.nextInt();
int C = sc.nextInt();
char[][] grid = new char[R][C];
int startX = -1, startY = -1; // 乔的起始位置
Queue<int[]> fireQueue = new LinkedList<>(); // 存储所有火焰的初始位置
// 读入地图，并记录乔的位置和所有火焰位置
for (int i = 0; i < R; i++) {
String line = sc.next();
for (int j = 0; j < C; j++) {
grid[i][j] = line.charAt(j);
if (grid[i][j] == 'J') {
startX = i;
startY = j;
}
if (grid[i][j] == 'F') {
fireQueue.offer(new int[]{i, j}); // 把火焰加入队列
}
}
}
// ========== 第一步：BFS 计算火蔓延到每个格子的最早时间 ==========
int[][] fireTime = new int[R][C];
// 初始化为最大值，表示“未被点燃”
for (int i = 0; i < R; i++) {
Arrays.fill(fireTime[i], Integer.MAX_VALUE);
}
// 多源 BFS：所有 F 同时开始蔓延
while (!fireQueue.isEmpty()) {
int[] pos = fireQueue.poll();
int x = pos[0], y = pos[1];
// 如果是初始火焰，设时间为 0
if (fireTime[x][y] == Integer.MAX_VALUE) {
fireTime[x][y] = 0;
}
// 向四个方向蔓延
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
// 检查是否越界、是否是墙、是否已经处理过
if (nx >= 0 && nx < R && ny >= 0 && ny < C
&& grid[nx][ny] != '#'
&& fireTime[nx][ny] == Integer.MAX_VALUE) {
// 火蔓延到 (nx, ny) 的时间 = 当前时间 + 1
fireTime[nx][ny] = fireTime[x][y] + 1;
fireQueue.offer(new int[]{nx, ny});
}
}
}
// ========== 第二步：BFS 模拟乔的移动 ==========
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[R][C]; // 防止重复访问
// 起点入队，格式：{x, y, 当前时间}
queue.offer(new int[]{startX, startY, 0});
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] state = queue.poll();
int x = state[0], y = state[1], time = state[2];
// 检查是否站在边界上：如果是，再花 1 秒就能逃出
if (x == 0 || x == R - 1 || y == 0 || y == C - 1) {
System.out.println(time + 1);
return;
}
// 尝试向四个方向移动
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
// 检查是否越界、是否是墙、是否已访问
if (nx >= 0 && nx < R && ny >= 0 && ny < C
&& grid[nx][ny] != '#'
&& !visited[nx][ny]) {
// 关键安全判断：乔在 time+1 时刻到达 (nx, ny)
// 必须保证此时该格子还未着火（即 fireTime > time+1）
if (fireTime[nx][ny] > time + 1) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny, time + 1});
}
}
}
}
// 如果 BFS 结束都没逃出，说明不可能
System.out.println("IMPOSSIBLE");
}
}
关键说明
- 火的 BFS：从所有
F同时开始，记录每个格子最早被点燃的时间； - 人的 BFS：从
J开始，每一步检查下一步是否会在下一时刻被火烧到； - 边界条件：一旦走到边界，再花 1 时间逃脱；
- 状态设计：
{x, y, time}表示当前位置和当前时间； - 剪枝：已访问过的位置不再重复处理。
餐厅
解题思路
在一个 n \times m 的网格地图中，小Y（Y）和小M（M）分别位于不同位置。地图包含：
.：空地，可通行；#：障碍，不可进入；@：餐厅（可能多个），两人必须在同一个餐厅会面。
每次移动一格耗时 11 分钟，可上下左右移动。
目标是选择一个餐厅，使得两人从起点到达该餐厅的总时间最小。
核心思想
由于每步代价相同，问题转化为：
- 分别计算小Y和小M到所有点的最短步数；
- 枚举每个餐厅
@，若两人都能到达，则计算总步数； - 取最小总步数 × 11 作为答案。
✅ 关键：必须确保两人均能到达该餐厅，否则跳过。
算法步骤
- 读入地图，记录
Y和M的坐标； - BFS 从 Y 出发，得到
distY[i][j]：Y 到(i,j)的最短步数； - BFS 从 M 出发，得到
distM[i][j]：M 到(i,j)的最短步数； - 遍历所有
@：- 若
distY[i][j]和distM[i][j]均非无穷大，则更新最小总步数；
- 若
- 输出
minTotalSteps × 11。
参考代码（Java）
import java.util.*;
public class Main {
// 四个方向：右、左、下、上
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
char[][] grid = new char[n][m];
int yX = -1, yY = -1; // 小Y的起始坐标
int mX = -1, mY = -1; // 小M的起始坐标
// 读取地图，同时定位 Y 和 M
for (int i = 0; i < n; i++) {
String line = sc.next();
for (int j = 0; j < m; j++) {
grid[i][j] = line.charAt(j);
if (grid[i][j] == 'Y') {
yX = i;
yY = j;
} else if (grid[i][j] == 'M') {
mX = i;
mY = j;
}
}
}
// 分别从 Y 和 M 出发进行 BFS，计算到每个点的最短距离
int[][] distY = bfs(grid, n, m, yX, yY);
int[][] distM = bfs(grid, n, m, mX, mY);
// 初始化最小总步数为最大值
int minTotalSteps = Integer.MAX_VALUE;
// 遍历整个地图，寻找所有餐厅 '@'
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '@') {
// 关键检查：只有当两人都能到达该餐厅时才考虑
if (distY[i][j] != Integer.MAX_VALUE && distM[i][j] != Integer.MAX_VALUE) {
int totalSteps = distY[i][j] + distM[i][j];
if (totalSteps < minTotalSteps) {
minTotalSteps = totalSteps;
}
}
}
}
}
// 总时间 = 总步数 × 每步 11 分钟
System.out.println(minTotalSteps * 11);
}
/**
* 从指定起点 (startX, startY) 开始 BFS，计算到所有可达点的最短步数
* @param grid 地图
* @param n 行数
* @param m 列数
* @param startX 起点行坐标
* @param startY 起点列坐标
* @return 二维数组 dist，dist[i][j] 表示从起点到 (i,j) 的最短步数，
* 若不可达则为 Integer.MAX_VALUE
*/
private static int[][] bfs(char[][] grid, int n, int m, int startX, int startY) {
// 初始化距离数组，全部设为不可达
int[][] dist = new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
Queue<int[]> queue = new LinkedList<>();
// 起点距离为 0，并加入队列
dist[startX][startY] = 0;
queue.offer(new int[]{startX, startY});
while (!queue.isEmpty()) {
int[] pos = queue.poll();
int x = pos[0], y = pos[1];
// 尝试四个方向移动
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
// 检查新位置是否合法：不越界、不是墙、且未被访问过
if (nx >= 0 && nx < n && ny >= 0 && ny < m
&& grid[nx][ny] != '#'
&& dist[nx][ny] == Integer.MAX_VALUE) {
// 更新距离，并将新位置加入队列
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
return dist;
}
}
关键说明
- BFS 正确性：因为每步代价相同，BFS 天然求出最短路径；
- 安全判断：必须同时满足
distY[i][j]和distM[i][j]可达，避免无效餐厅； - 效率：两次 BFS 时间复杂度均为 O(nm)，总复杂度 O(nm)，适用于 n, m \leq 200；
- 输出：题目保证至少存在一个两人均可到达的餐厅，因此无需处理无解情况。
星际旅行
解题思路
小明在由 n 个星球和 m 条双向传送门构成的星系中旅行。
他有 Q 个“旅游盲盒”，每个盲盒指定：
- 起始星球 x_i
- 最多可使用传送门的次数 y_i
每次使用传送门算作 1 步，目标是：对每个盲盒，统计从 x_i 出发、最多走 y_i 步所能到达的不同星球数量（包括起点）。
最终输出所有盲盒结果的平均值（期望），保留两位小数。
为什么用 BFS？
- 所有边权为 1（每步代价相同）；
- 需要知道“在 k 步内能到达哪些点”；
- BFS 天然按层数（步数）扩展，能精确控制最大步数。
不需要 Dijkstra，因为没有权重差异；也不需要 Floyd 或 DFS（DFS 无法保证最小步数）。
算法步骤
- 建图：使用邻接表存储无向图；
- 对每个盲盒独立处理：
- 从起始星球开始 BFS；
- 记录每个星球首次被访问时的步数；
- 若当前步数 ≤ y_i ，则计入答案；
- 累加所有盲盒的可达星球数，除以 Q 得期望。
参考代码（Java）
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 星球数量
int m = sc.nextInt(); // 传送门数量
int Q = sc.nextInt(); // 盲盒数量
// 构建邻接表：adj[i] 存储与星球 i 相连的所有星球
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
// 读入 m 条无向边
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
adj.get(a).add(b);
adj.get(b).add(a); // 双向连接
}
double total = 0.0; // 所有盲盒可达星球总数（用于求平均）
// 逐个处理每个盲盒
for (int i = 0; i < Q; i++) {
int start = sc.nextInt(); // 起始星球
int maxSteps = sc.nextInt(); // 最大允许步数
// visited 数组：防止重复访问同一星球
boolean[] visited = new boolean[n + 1];
// 队列中存储 {当前星球, 到达该星球所用的步数}
Queue<int[]> queue = new LinkedList<>();
// 起点入队，步数为 0（站在起点也算一次访问）
queue.offer(new int[]{start, 0});
visited[start] = true;
int count = 0; // 当前盲盒可到达的星球数量
while (!queue.isEmpty()) {
int[] state = queue.poll();
int node = state[0];
int steps = state[1];
// 如果当前步数已超过限制，跳过
if (steps > maxSteps) {
continue;
}
// 每个新访问的节点都算一个可达星球
count++;
// 遍历所有相邻星球
for (int neighbor : adj.get(node)) {
// 如果邻居未被访问过，则标记并入队
if (!visited[neighbor]) {
visited[neighbor] = true;
// 下一步的步数是当前步数 + 1
// 只有当 steps + 1 <= maxSteps 时才可能有用，但即使超过，
// 我们也可以入队并在出队时跳过（逻辑统一）
queue.offer(new int[]{neighbor, steps + 1});
}
}
}
total += count;
}
// 计算期望值：总可达数 / 盲盒数量
double expectation = total / Q;
// 保留两位小数输出
System.out.printf("%.2f\n", expectation);
}
}
时间复杂度
- 建图： O(m)
- 每个盲盒 BFS：最坏 O(n + m)
- 总复杂度： O(Q \cdot (n + m))
对于 n, m \leq 10^4 、 Q \leq 10^5 ，在 Java 中可接受（实际常数较小）。
爆破
解题思路
有 n 个圆形魔法阵，第 i 个的圆心为 (x_i, y_i) ，半径为 r_i 。
- 如果两个魔法阵相交或相切（即圆心距离 ≤ 半径之和），它们会自动引爆，无需额外连接；
- 否则，需要用一条魔法回路连接它们的边缘，长度为两圆之间的最短间隙。
目标：用总长度最小的魔法回路，使得所有魔法阵最终都能被引爆（即整个图连通）。
✅ 本质：在一个完全图上求 最小生成树（MST），边权为两圆之间的最短间隙。
对于任意两个魔法阵 i 和 j ：
-
圆心距离：
d_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} -
所需魔法回路长度（边权）：
w_{ij} = \max(d_{ij} - (r_i + r_j),\ 0)
- 若 d_{ij} \leq r_i + r_j ，两圆相交/相切 → w_{ij} = 0 ；
- 否则，需连接外部间隙 → w_{ij} = d_{ij} - r_i - r_j 。
由于任意两点之间都有边，这是一个稠密图（最多约 1.25 \times 10^7 条边），因此应使用 Prim 算法（ O(n^2) ） 而非 Kruskal。
算法选择：Prim（适用于稠密图）
- 时间复杂度： O(n^2)
- 空间复杂度： O(n^2) （存储邻接矩阵）
- 对于 n \leq 5000 ， n^2 = 25 \times 10^6 ，在 Java 中可接受（注意使用
double数组，约 200 MB，部分 OJ 可能卡内存，但题目通常允许）
💡 实际中可优化为不显式建图，而是在 Prim 过程中动态计算边权，从而将空间降至 O(n) 。但为了清晰，此处先采用标准邻接矩阵写法。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 使用三个数组分别存储 x, y, r
double[] x = new double[n];
double[] y = new double[n];
double[] r = new double[n];
// 读入每个魔法阵的参数
for (int i = 0; i < n; i++) {
x[i] = sc.nextDouble();
y[i] = sc.nextDouble();
r[i] = sc.nextDouble();
}
// 特判：只有一个魔法阵，无需连接
if (n == 1) {
System.out.println("0.00");
return;
}
// 构建邻接矩阵 graph[i][j] 表示 i 和 j 之间的魔法回路长度
double[][] graph = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 计算圆心之间的欧几里得距离
double dx = x[i] - x[j];
double dy = y[i] - y[j];
double centerDist = Math.sqrt(dx * dx + dy * dy);
// 边权 = max(圆心距 - 半径和, 0)
double weight = Math.max(centerDist - (r[i] + r[j]), 0.0);
// 无向图，对称赋值
graph[i][j] = weight;
graph[j][i] = weight;
}
}
// 使用 Prim 算法求最小生成树的总权重
double totalLength = prim(graph, n);
// 输出结果，保留两位小数
System.out.printf("%.2f\n", totalLength);
}
/**
* Prim 算法求最小生成树（MST）的总权重
* @param graph 邻接矩阵，graph[i][j] 表示节点 i 和 j 之间的边权
* @param n 节点总数
* @return MST 的总边权
*/
private static double prim(double[][] graph, int n) {
// minEdge[i]：当前 MST 到节点 i 的最小边权
double[] minEdge = new double[n];
// used[i]：节点 i 是否已加入 MST
boolean[] used = new boolean[n];
// 初始化：从节点 0 开始构建 MST
Arrays.fill(minEdge, Double.MAX_VALUE);
minEdge[0] = 0.0;
double totalWeight = 0.0;
// 共需加入 n 个节点
for (int iter = 0; iter < n; iter++) {
// 在未加入 MST 的节点中，找到 minEdge 最小的节点 u
int u = -1;
for (int i = 0; i < n; i++) {
if (!used[i] && (u == -1 || minEdge[i] < minEdge[u])) {
u = i;
}
}
// 将 u 加入 MST
used[u] = true;
totalWeight += minEdge[u];
// 用 u 更新其他未加入节点到 MST 的最小边权
for (int v = 0; v < n; v++) {
if (!used[v] && graph[u][v] < minEdge[v]) {
minEdge[v] = graph[u][v];
}
}
}
return totalWeight;
}
}
关键步骤详解
| 步骤 | 说明 |
|---|---|
| 输入处理 | 用三个 double[] 数组分别存 x_i, y_i, r_i ，更简洁 |
| 边权计算 | 对每对 (i,j) ，计算 \max(\text{圆心距} - (r_i + r_j), 0) |
| 邻接矩阵 | 因为是完全图，直接用 graph[i][j] 存储边权 |
| Prim 初始化 | 从节点 0 开始，minEdge[0] = 0，其余为无穷大 |
| 贪心选点 | 每次从未加入集合中选 minEdge 最小的点，加入 MST |
| 松弛更新 | 用新加入的点 u 去更新其他点到 MST 的最短边 |
| 输出格式 | 使用 printf("%.2f") 保留两位小数 |
- 时间复杂度：
- 建图： O(n^2)
- Prim： O(n^2)
- 总计： O(n^2) ，对 n = 5000 约 2500 万次操作，Java 可通过
电动车
解题思路
有 N 座城市和 M 条双向高速公路。
每条高速公路连接两个城市 u, v ，行驶一次消耗 w 单位电量。
电动车可以在任意城市充满电，但在高速公路上不能充电。
因此，若某条路耗电为 w ，则电池容量必须 ≥ w 才能通过。
✅ 目标：求出最小的电池容量，使得从任意城市出发，都能到达其他所有城市。
如果图不连通，则输出 -1。
- 由于可以在城市无限充电，路径总耗电不重要，关键在于路径中单条边的最大耗电量。
- 要使任意两城可达，整个图必须连通；
- 我们希望选择一组边构成生成树，使得其中最大边权尽可能小。
💡 这正是 最小瓶颈生成树（Minimum Bottleneck Spanning Tree） 问题。
而经典结论是：
最小生成树（MST）就是最小瓶颈生成树。
因此，只需构造图的 MST，并找出其中最大的边权值，即为答案。
算法选择：Kruskal + 并查集
- 将所有边按权重从小到大排序；
- 用并查集依次加入边，直到形成生成树（共 N-1 条边）；
- 记录加入过程中最大的那条边的权重；
- 若最终边数不足 N-1 ，说明图不连通，输出
-1。
✅ 优势：天然按边权递增顺序处理，最大边权即最后加入的边中最大的那个。
参考代码
import java.util.*;
public class Main {
// 并查集类：用于判断连通性和合并集合
static class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
}
// 路径压缩查找根节点
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个集合，返回是否成功合并（即是否原本不连通）
public boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
parent[rx] = ry;
return true;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 城市数量
int M = sc.nextInt(); // 高速公路数量
// 使用二维数组 edges 存储所有边：edges[i] = {u, v, w}
int[][] edges = new int[M][3];
for (int i = 0; i < M; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
edges[i][0] = u;
edges[i][1] = v;
edges[i][2] = w;
}
// 按边权 w 升序排序（Kruskal 的关键步骤）
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
// 初始化并查集
UnionFind uf = new UnionFind(N);
int maxBattery = 0; // 记录 MST 中的最大边权（即所需最小电池容量）
int edgeCount = 0; // 已加入 MST 的边数
// 遍历所有边（已按权重从小到大排序）
for (int i = 0; i < M; i++) {
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
// 如果 u 和 v 不在同一连通分量，则加入这条边
if (uf.union(u, v)) {
maxBattery = Math.max(maxBattery, w); // 更新最大边权
edgeCount++;
// 当已选 N-1 条边时，生成树完成，可提前退出
if (edgeCount == N - 1) {
break;
}
}
}
// 判断是否连通：若边数不足 N-1，说明图不连通
if (edgeCount != N - 1) {
System.out.println(-1);
} else {
System.out.println(maxBattery);
}
}
}
- 时间复杂度：
- 排序： O(M \log M)
- 并查集操作：近似 O(M \alpha(N)) ，其中 \alpha 是阿克曼反函数，可视为常数
- 总计： O(M \log M)
- 空间复杂度： O(N + M)
对于 N \leq 10^5, M \leq 2 \times 10^5 ，完全可行。
