C++ 实现带路障棋盘棋子移动问题求解

以下是使用 C++ 语言解决该问题的代码： ```cpp #include <iostream> #include <queue> #include <vector> #include <utility> using namespace std; // 定义方向数组，分别表示上、下、左、右 const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; // 检查坐标 (x, y) 是否在棋盘内 bool isValid(int x, int y, int n) { return x >= 1 && x <= n && y >= 1 && y <= n; } // 广度优先搜索函数 bool bfs(int n, vector<pair<int, int>>& obstacles) { // 定义队列用于 BFS queue<pair<pair<int, int>, int>> q; // 初始状态，棋子位于 (1, 1)，时间为 0 q.push({{1, 1}, 0}); // 定义访问数组，用于记录每个位置在每个时间是否被访问过 vector<vector<vector<bool>>> visited(n + 1, vector<vector<bool>>(n + 1, vector<bool>(2 * n - 1, false))); visited[1][1][0] = true; while (!q.empty()) { // 取出队首元素 auto [pos, time] = q.front(); auto [x, y] = pos; q.pop(); // 如果到达终点，返回 true if (x == n && y == n) { return true; } // 检查下一步的四个方向 for (int i = 0; i < 4; ++i) { int newX = x + dx[i]; int newY = y + dy[i]; int newTime = time + 1; // 检查新位置是否合法，是否有障碍物，是否未被访问过 if (isValid(newX, newY, n) && (newTime >= obstacles.size() || (newX != obstacles[newTime].first || newY != obstacles[newTime].second)) && !visited[newX][newY][newTime]) { // 标记新位置为已访问 visited[newX][newY][newTime] = true; // 将新状态加入队列 q.push({{newX, newY}, newTime}); } } } // 未到达终点，返回 false return false; } int main() { int n; cin >> n; // 存储障碍物信息 vector<pair<int, int>> obstacles(2 * n - 2); for (int i = 0; i < 2 * n - 2; ++i) { cin >> obstacles[i].first >> obstacles[i].second; } // 调用 BFS 函数进行搜索 if (bfs(n, obstacles)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } ``` ### 代码解释： 1. **方向数组**：`dx` 和 `dy` 数组用于表示棋子可以移动的四个方向（上、下、左、右）。 2. **isValid 函数**：用于检查给定的坐标 `(x, y)` 是否在棋盘内。 3. **bfs 函数**：使用广度优先搜索算法来搜索从 `(1, 1)` 到 `(n, n)` 的路径。在搜索过程中，需要考虑每个时间点的障碍物信息。 4. **visited 数组**：用于记录每个位置在每个时间是否被访问过，避免重复访问。 5. **main 函数**：读取输入的棋盘大小和障碍物信息，调用 `bfs` 函数进行搜索，并输出结果。 ### 复杂度分析： - **时间复杂度**：$O(n^3)$，因为在最坏情况下，需要遍历每个位置在每个时间点的状态。 - **空间复杂度**：$O(n^3)$，主要用于存储访问数组。 ######[AI问答 | 976点数解答 | 2026-03-03 19:14:37]