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

```cpp #include <iostream> #include <queue> #include <vector> using namespace std; // 定义一个结构体表示状态，包含棋子位置和时间 struct State { int x, y, time; State(int _x, int _y, int _t) : x(_x), y(_y), time(_t) {} }; // 检查坐标是否在棋盘内 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) { // 定义四个方向：上、下、左、右 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; // 标记数组，用于记录某个状态是否已经访问过 vector<vector<vector<bool>>> visited(n + 1, vector<vector<bool>>(n + 1, vector<bool>(2 * n - 1, false))); // 初始化队列，将起始状态加入队列 queue<State> q; q.push(State(1, 1, 0)); visited[1][1][0] = true; while (!q.empty()) { // 取出队首元素 State current = q.front(); q.pop(); int x = current.x; int y = current.y; int time = current.time; // 如果到达终点，返回 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 - 1].first || newY != obstacles[newTime - 1].second)) && !visited[newX][newY][newTime]) { // 将新状态加入队列并标记为已访问 q.push(State(newX, newY, newTime)); visited[newX][newY][newTime] = true; } } } // 无法到达终点，返回 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. **结构体 `State`**：用于表示棋子的状态，包含当前位置 `(x, y)` 和时间 `time`。 2. **`isValid` 函数**：用于检查一个坐标是否在 `n * n` 的棋盘范围内。 3. **`bfs` 函数**：使用广度优先搜索算法来寻找从 `(1, 1)` 到 `(n, n)` 的路径。 - 定义四个移动方向 `dx` 和 `dy`。 - 使用三维标记数组 `visited` 来记录某个状态是否已经访问过。 - 初始化队列 `q`，将起始状态加入队列。 - 不断从队列中取出元素，尝试四个方向的移动，检查新位置是否合法、是否有障碍物、是否未被访问过，若满足条件则将新状态加入队列。 4. **`main` 函数**： - 读取输入的 `n` 和障碍物信息。 - 调用 `bfs` 函数并根据结果输出 `Yes` 或 `No`。 ######[AI问答 | 1013点数解答 | 2026-03-07 19:13:59]