题目描述

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

输入

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

输出

卒的行走路线

样例输入 复制

3 3

样例输出 复制

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

 代码：

#include <bits/stdc++.h>
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() {cin>>n>>m;dfs(1,1,0);return 0;
}