C++实现马在棋盘上最少步数的计算

以下是使用 C++ 实现计算马从点 `(x, y)` 到达棋盘上任意一个点最少要走几步的代码： ```cpp #include <iostream> #include <queue> #include <cstring> using namespace std; const int MAXN = 405; int n, m, x, y; int dist[MAXN][MAXN]; // 存储马到达每个点的最少步数 bool visited[MAXN][MAXN]; // 标记点是否已经访问过 // 马的 8 个可能移动方向 int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; // 广度优先搜索函数 void bfs(int startX, int startY) { queue<pair<int, int>> q; q.push({startX, startY}); dist[startX][startY] = 0; visited[startX][startY] = true; while (!q.empty()) { auto [curX, curY] = q.front(); q.pop(); // 遍历马的 8 个可能移动方向 for (int i = 0; i < 8; ++i) { int newX = curX + dx[i]; int newY = curY + dy[i]; // 判断新位置是否在棋盘内且未被访问过 if (newX >= 1 && newX <= n && newY >= 1 && newY <= m && !visited[newX][newY]) { dist[newX][newY] = dist[curX][curY] + 1; visited[newX][newY] = true; q.push({newX, newY}); } } } } int main() { cin >> n >> m >> x >> y; // 初始化距离数组为 -1，表示不能到达 memset(dist, -1, sizeof(dist)); memset(visited, false, sizeof(visited)); // 从起始点开始进行广度优先搜索 bfs(x, y); // 输出结果矩阵 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cout.width(5); // 设置输出宽度为 5 cout << dist[i][j]; } cout << endl; } return 0; } ``` ### 代码解释： 1. **输入处理**：读取棋盘的大小 `n` 和 `m`，以及马的起始位置 `(x, y)`。 2. **初始化**：使用 `memset` 函数将 `dist` 数组初始化为 -1，表示不能到达；将 `visited` 数组初始化为 `false`，表示所有点都未被访问过。 3. **广度优先搜索（BFS）**：从起始点 `(x, y)` 开始进行 BFS，使用队列存储待访问的点。每次从队列中取出一个点，遍历其 8 个可能的移动方向，如果新位置在棋盘内且未被访问过，则更新 `dist` 数组，并将新位置加入队列。 4. **输出结果**：遍历整个棋盘，输出马到达每个点的最少步数。 ### 复杂度分析： - **时间复杂度**：$O(nm)$，因为每个点最多被访问一次。 - **空间复杂度**：$O(nm)$，主要用于存储 `dist` 数组和 `visited` 数组。 ######[AI问答 | 873点数解答 | 2026-04-29 20:21:41]