问题描述
给定一个二维地图，其中包含起点 S、终点 E、障碍物 #、宝石 0 到 4、以及传送门 $。要求从起点 S 出发，找到最短路径到达终点 E，并收集至少 K 种宝石。你可以通过传送门在不同位置之间跳跃，求出最短步数。若无法达到终点并收集足够的宝石，则输出 "oop!"。
思路分析
1. 状态表示
我们使用 BFS 来搜索最短路径。为了能够记录不同状态下的路径，我们定义了 State 结构体来保存当前的位置 (x, y)、当前收集的宝石状态 (gems)，以及已经走过的步数 (steps)。
gems使用二进制位表示，gems & (1 << i)用来表示是否收集了宝石i。gems总共有 32 种状态，最多收集 5 种宝石。
2. BFS 搜索
在 BFS 的过程中，我们遍历每一个可行的方向（上下左右），并且更新宝石状态。每次经过宝石时，更新 gems 状态。如果当前位置是传送门，则尝试跳跃到其他传送门。
- 如果到达终点
E且收集了至少K种宝石，则返回步数。 - 如果没有找到解，返回
-1。
3. 传送门处理
传送门是一个特殊的情况，任何经过传送门的位置都可以跳跃到其他传送门的位置。
代码实现
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct State {
int x, y, gems, steps;
};
const int MAXN = 200;
char grid[MAXN][MAXN]; // 地图
int dist[MAXN][MAXN][32]; // 记录最短路径
int dx[4] = { 0, 0, -1, 1 }; // 四个方向
int dy[4] = { -1, 1, 0, 0 };
int bfs(int R, int C, int K) {
queue<State> q;
int ex, ey;
vector<pair<int, int>> portals; // 记录传送门位置
// 初始化 dist 数组
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
for (int k = 0; k < 32; k++) dist[i][j][k] = -1;
// 处理输入并找到起点、终点、传送门
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (grid[i][j] == 'S') {
q.push({ i, j, 0, 0 });
dist[i][j][0] = 0;
} else if (grid[i][j] == 'E') {
ex = i, ey = j;
} else if (grid[i][j] == '$') {
portals.push_back({ i, j });
}
}
}
// BFS 搜索
while (!q.empty()) {
State cur = q.front();
q.pop();
int x = cur.x, y = cur.y, gems = cur.gems, steps = cur.steps;
// 终点条件：到达 E 并且集齐 K 种宝石
if (x == ex && y == ey && __builtin_popcount(gems) >= K) {
return steps;
}
// 4 个方向移动
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d], ngems = gems;
if (nx < 0 || nx >= R || ny < 0 || ny >= C || grid[nx][ny] == '#')
continue;
// 如果是宝石，更新宝石状态
if ('0' <= grid[nx][ny] && grid[nx][ny] <= '4') {
ngems |= (1 << (grid[nx][ny] - '0'));
}
// 该状态未访问过
if (dist[nx][ny][ngems] == -1) {
dist[nx][ny][ngems] = steps + 1;
q.push({ nx, ny, ngems, steps + 1 });
}
}
// 传送门跳跃
if (grid[x][y] == '$') {
for (int i = 0; i < portals.size(); i++) {
int px = portals[i].first, py = portals[i].second;
if ((px != x || py != y) && dist[px][py][gems] == -1) {
dist[px][py][gems] = steps;
q.push({ px, py, gems, steps });
}
}
}
}
return -1; // 无法救出公主
}
int main() {
int T;
cin >> T;
while (T--) {
int R, C, K;
cin >> R >> C >> K;
for (int i = 0; i < R; i++) {
cin >> grid[i];
}
int result = bfs(R, C, K);
if (result == -1) {
cout << "oop!" << endl;
} else {
cout << result << endl;
}
}
return 0;
}
代码解析
1. State 结构体
```cpp
struct State {
int x, y, gems, steps;
};
State 结构体用于存储 BFS 搜索中的状态，包括：
x, y：当前位置。 gems：表示已经收集的宝石种类。 steps：到达当前状态所需的步数。 2. bfs 函数
int bfs(int R, int C, int K) {
// ...
}
初始化 BFS 搜索队列和 dist 数组，表示每个位置、宝石状态下的最短步数。 处理地图输入，找到起点 S、终点 E 和所有传送门的位置。 使用 BFS 进行搜索，遍历四个方向并更新宝石状态。 处理传送门的特殊情况，如果当前位置是传送门，则尝试跳跃到其他传送门。 3. main 函数
int main() {
int T;
cin >> T;
while (T--) {
int R, C, K;
cin >> R >> C >> K;
for (int i = 0; i < R; i++) {
cin >> grid[i];
}
int result = bfs(R, C, K);
if (result == -1) {
cout << "oop!" << endl;
} else {
cout << result << endl;
}
}
return 0;
}
主函数用于读取多组测试数据，调用 bfs 函数进行计算并输出结果。如果无法收集足够的宝石，则输出 "oop!"。
总结 本题的关键在于通过 BFS 算法进行状态空间搜索，并巧妙地使用二进制位表示收集的宝石种类，从而避免了对每个宝石种类的重复计算。此外，处理传送门的跳跃也为解法增添了难度。
共 2 条回复