解题思路

马从棋盘左下角 (0,0) 跳到右上角 (4,8)，只能往右跳，按顺时针方向尝试，输出所有可能的跳法。

思路：深度优先搜索。

1. 记录当前路径，从起点开始
2. 按顺时针顺序尝试 4 个往右跳的方向：
   • 右上 (2,1)、右 (1,2)、右偏下 (-1,2)、右下 (-2,1)
3. 新位置在棋盘范围内就继续跳
4. 跳到终点 (4,8) 就输出这条路径

方向为什么是这 4 个？ 马走日字，往右跳只有 4 种可能：(2,1)、(1,2)、(-1,2)、(-2,1)。按顺时针排列就是搜索顺序。

输出格式：路径编号 + 用 -> 连接的所有经过点，最后到 4,8。

参考代码

#include <iostream>
using namespace std;

int a[110][110], t;
int dx[4] = {2, 1, -1, -2};
int dy[4] = {1, 2, 2, 1};

void dfs(int k) {
    for (int i = 0; i <= 3; i++) {
        a[k][1] = a[k - 1][1] + dx[i];
        a[k][2] = a[k - 1][2] + dy[i];

        if (a[k][1] >= 0 && a[k][1] <= 4 && a[k][2] >= 0 && a[k][2] <= 8) {
            if (a[k][1] == 4 && a[k][2] == 8) {  // 到终点
                t++;
                cout << t << ":";
                for (int j = 1; j < k; j++) {
                    cout << a[j][1] << "," << a[j][2] << "->";
                }
                cout << "4,8" << endl;
            } else {
                dfs(k + 1);
            }
        }
    }
}

int main() {
    a[1][1] = 0;
    a[1][2] = 0;
    dfs(2);
}

复杂度分析

• 时间复杂度：O(4^N)，每步 4 个方向
• 空间复杂度：O(N)，路径和递归深度