说明

在一张n*m的棋盘上（如6行7列）的最左上角（1,1）的位置有一个卒。该卒只能向下或者向右走，且卒采取的策略是先向下，下边走到头就向右，请问从（1,1）点走到（n,m）点可以怎样走，输出这些走法。

输入格式

两个整数n，m代表棋盘大小（3=<n<=8,3<=m<=8）

输出格式

卒的行走路线

样例

输入数据 1

3 3

Copy

输出数据 1

1:1,1->2,1->3,1->3,2->3,3
2:1,1->2,1->2,2->3,2->3,3
3:1,1->2,1->2,2->2,3->3,3
4:1,1->1,2->2,2->3,2->3,3
5:1,1->1,2->2,2->2,3->3,3
6:1,1->1,2->1,3->2,3->3,3

dfs模板

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
using namespace std;
int n,m,ans=0,vis[15][15];
int dx[4]= {1,0},dy[4]= {0,1};
struct te {
    int dx;
    int dy;
};
te a[20];
void dfs(int x,int y,int step) {
    if(x==n&&y==m) {
        a[step].dx=x;
        a[step].dy=y;
        ans++;
        cout<<ans<<":"<<a[0].dx<<","<<a[0].dy;
        for(int i=1; i<=step; i++) {
        cout<<"->"<<a[i].dx<<","<<a[i].dy;
        }
        cout<<endl;
    }
    vis[x][y]=1;
    a[step].dx=x;
    a[step].dy=y;
    for(int i=0; i<2; i++) {
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>0&&ty>0&&tx<=n&&ty<=m&&vis[tx][ty]==0) {
            step++;
            dfs(tx,ty,step);
            vis[tx][ty]=0;
            step--;
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    dfs(1,1,0);
    return 0;
}