神奇空间房间传送门最少经过数量的C++实现

```cpp #include <iostream> #include <vector> #include <queue> #include <sstream> #include <unordered_set> using namespace std; // 广度优先搜索函数，用于计算从房间A到房间B最少经过的传送门数量 int bfs(const vector<vector<int>>& rooms, int A, int B) { int n = rooms.size(); vector<bool> visited(n, false); queue<pair<int, int>> q; q.push({A - 1, 0}); visited[A - 1] = true; while (!q.empty()) { auto [current_room, steps] = q.front(); q.pop(); if (current_room == B - 1) { return steps; } // 遍历当前房间的所有传送门 for (int portal : rooms[current_room]) { for (int i = 0; i < n; ++i) { if (i != current_room && !visited[i]) { // 检查其他房间是否有相同编号的传送门 for (int other_portal : rooms[i]) { if (other_portal == portal) { q.push({i, steps + 1}); visited[i] = true; break; } } } } } } return -1; } int main() { int N; cin >> N; cin.ignore(); // 忽略换行符 vector<vector<int>> rooms(N); for (int i = 0; i < N; ++i) { string line; getline(cin, line); stringstream ss(line); string token; while (getline(ss, token, ',')) { rooms[i].push_back(stoi(token)); } } int A, B; char comma; cin >> A >> comma >> B; int result = bfs(rooms, A, B); cout << result << endl; return 0; } ``` ### 代码解释： 1. **输入处理**： - 首先读取房间数量`N`。 - 接着循环`N`次，每次读取一行传送门编号，使用`stringstream`将其分割成整数并存储到`rooms`向量中。 - 最后读取出发房间编号`A`和目标房间编号`B`。 2. **广度优先搜索（BFS）**： - 使用队列`q`存储待访问的房间和经过的传送门数量。 - 使用`visited`数组标记房间是否已访问。 - 从房间`A`开始，将其加入队列并标记为已访问。 - 每次从队列中取出一个房间，检查是否到达目标房间`B`，如果到达则返回经过的传送门数量。 - 遍历当前房间的所有传送门，检查其他未访问的房间是否有相同编号的传送门，如果有则将该房间加入队列并标记为已访问。 3. **输出结果**： - 如果能到达目标房间，返回最少经过的传送门数量；否则返回 -1。 ######[AI问答 | 760点数解答 | 2026-02-14 20:12:39]