使用 C++ 实现马在棋盘上不重复遍历的解决方案

以下是使用 C++ 实现的代码，用于解决在 `n * n` 棋盘上，马从指定位置出发，不重复地走遍棋盘上每一个点的问题： ```cpp #include <iostream> #include <iomanip> #include <cstring> using namespace std; const int MAXN = 6; int n; int board[MAXN][MAXN]; int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2}; int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; // 深度优先搜索函数 bool dfs(int x, int y, int step) { // 判断当前位置是否越界、是否已经走过 if (x < 0 || x >= n || y < 0 || y >= n || board[x][y] != 0) { return false; } // 标记当前位置为已走过，并记录步数 board[x][y] = step; // 如果已经走完所有格子，返回 true if (step == n * n) { return true; } // 尝试 8 个可能的方向 for (int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (dfs(nx, ny, step + 1)) { return true; } } // 如果 8 个方向都走不通，回溯 board[x][y] = 0; return false; } int main() { cin >> n; int startX, startY; cin >> startX >> startY; // 初始化棋盘 memset(board, 0, sizeof(board)); // 从起始位置开始深度优先搜索 if (dfs(startX - 1, startY - 1, 1)) { // 输出棋盘 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << setw(3) << board[i][j]; if (j < n - 1) { cout << " "; } } cout << endl; } } else { cout << "NO answer!" << endl; } return 0; } ``` ### 代码解释： 1. **全局变量**： - `MAXN`：棋盘的最大边长。 - `n`：棋盘的实际边长。 - `board`：二维数组，用于记录棋盘上每个格子的状态。 - `dx` 和 `dy`：马走日字的 8 个可能方向。 2. **dfs 函数**： - 深度优先搜索函数，用于尝试从当前位置出发，找到一条不重复的路径。 - 如果当前位置越界或已经走过，返回 `false`。 - 标记当前位置为已走过，并记录步数。 - 如果已经走完所有格子，返回 `true`。 - 尝试 8 个可能的方向，如果某个方向可以走通，返回 `true`。 - 如果 8 个方向都走不通，回溯，将当前位置标记为未走过。 3. **main 函数**： - 读取输入的棋盘边长 `n` 和马的起始位置。 - 初始化棋盘。 - 从起始位置开始深度优先搜索。 - 如果找到路径，输出棋盘；否则，输出 `NO answer!`。 ######[AI问答 | 873点数解答 | 2026-03-28 21:07:22]