C++实现含路障的棋盘棋子移动问题编程解

以下是一个使用广度优先搜索（BFS）算法来解决该问题的 C++ 代码： ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; // 定义方向数组，分别表示上、下、左、右 const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; // 定义一个结构体来表示状态 struct State { int x, y; // 棋子的坐标 int time; // 当前时间 State(int _x, int _y, int _t) : x(_x), y(_y), time(_t) {} }; // 检查坐标 (x, y) 是否合法，是否越界或遇到路障 bool isValid(int x, int y, int n, const vector<vector<int>>& obstacles, int time) { return x >= 1 && x <= n && y >= 1 && y <= n && obstacles[time][x * (n + 1) + y] == 0; } // BFS 函数 int bfs(int n, const vector<vector<int>>& obstacles) { queue<State> q; // 标记数组，用于记录某个状态是否已经访问过 vector<vector<vector<bool>>> visited(n + 1, vector<vector<bool>>(n + 1, vector<bool>(n * n + 1, false))); // 初始状态入队 q.push(State(1, 1, 0)); visited[1][1][0] = true; while (!q.empty()) { State cur = q.front(); q.pop(); // 如果到达终点，返回当前时间 if (cur.x == n && cur.y == n) { return cur.time; } // 尝试向四个方向移动 for (int i = 0; i < 4; ++i) { int newX = cur.x + dx[i]; int newY = cur.y + dy[i]; int newTime = cur.time + 1; if (isValid(newX, newY, n, obstacles, newTime) && !visited[newX][newY][newTime]) { q.push(State(newX, newY, newTime)); visited[newX][newY][newTime] = true; } } } // 如果无法到达终点，返回 -1 return -1; } int main() { int n; cout << "请输入棋盘的大小 n: "; cin >> n; // 存储每一秒出现的路障信息 vector<vector<int>> obstacles(n * n + 1, vector<int>((n + 1) * (n + 1), 0)); cout << "请依次输入每一秒出现的路障坐标 (x y)，输入 -1 -1 结束：" << endl; int x, y; for (int t = 1; t <= n * n; ++t) { cin >> x >> y; if (x == -1 && y == -1) { break; } obstacles[t][x * (n + 1) + y] = 1; } int result = bfs(n, obstacles); if (result != -1) { cout << "到达终点所需的最短时间是: " << result << " 秒" << endl; } else { cout << "无法到达终点。" << endl; } return 0; } ``` ### 代码解释： 1. **结构体 `State`**：用于表示棋子的状态，包含棋子的坐标 `(x, y)` 和当前时间 `time`。 2. **`isValid` 函数**：用于检查某个坐标 `(x, y)` 是否合法，即是否越界或遇到路障。 3. **`bfs` 函数**：使用广度优先搜索算法来寻找从起点 `(1, 1)` 到终点 `(n, n)` 的最短路径。 4. **`main` 函数**：读取用户输入的棋盘大小 `n` 和每一秒出现的路障坐标，调用 `bfs` 函数计算最短时间并输出结果。 ### 复杂度分析： - **时间复杂度**：$O(n^3)$，因为需要遍历所有可能的时间和坐标。 - **空间复杂度**：$O(n^3)$，主要用于存储访问标记数组。 ######[AI问答 | 1071点数解答 | 2026-03-07 19:12:46]