解题思路

卒从棋盘左上角 (1,1) 走到右下角 (n,m)，只能向下或向右走，而且要先向下、再向右的顺序尝试，输出所有走法。

思路：深度优先搜索。

从起点开始，每一步尝试向下和向右两个方向：

1. 记录当前走过的路径
2. 先尝试向下走（如果没出界），递归
3. 再尝试向右走（如果没出界），递归
4. 走到终点就输出这条路径

为什么要先下后右？ 题目要求先向下、下边走到底就向右，所以搜索时先尝试向下，再尝试向右，这样输出的走法顺序就符合要求。

举例：3×3 棋盘有 6 种走法，比如 1,1→2,1→3,1→3,2→3,3。

参考代码

#include <iostream>
using namespace std;

int n, m, c;
int a[401][3];  // 记录路径

void dfs(int x, int y, int k) {
    a[k][1] = x;
    a[k][2] = y;

    if (x == n && y == m) {  // 到终点
        c++;
        cout << c << ":1,1";
        for (int i = 2; i <= k; i++) {
            cout << "->" << a[i][1] << "," << a[i][2];
        }
        cout << endl;
        return;
    }

    // 先向下，再向右
    if (x + 1 <= n) dfs(x + 1, y, k + 1);
    if (y + 1 <= m) dfs(x, y + 1, k + 1);
}

int main() {
    cin >> n >> m;
    dfs(1, 1, 1);
    return 0;
}

复杂度分析

• 时间复杂度：O(2^(n+m))，最多两种方向
• 空间复杂度：O(n+m)，路径和递归深度