【题目来源】
【题目描述】
中国象棋半张棋盘如图 (a) 所示。马自左下角往右上角跳。
今规定只许往右跳，不许往左跳，且要求马跳的方式按照 (b) 图顺时针深度优先递归。比如图 (a) 中所示为一种跳行路线。如果马要从 (0, 0) 点，跳到 (4, 8) 点，前6种跳法的打印格式如下，请参考前 6 种跳的方式，输出马从 (0, 0) 点到 (4, 8) 点所有可能的跳的路线。
1:0,0->2,1->4,2->3,4->4,6->2,7->4,8
2:0,0->2,1->4,2->3,4->1,5->3,6->4,8
3:0,0->2,1->4,2->3,4->1,5->2,7->4,8
4:0,0->2,1->4,2->2,3->4,4->3,6->4,8
5:0,0->2,1->4,2->2,3->4,4->2,5->4,6->2,7->4,8
6:0,0->2,1->4,2->2,3->4,4->2,5->0,6->2,7->4,8
【输入格式】
无
【输出格式】
按要求输出路径。
【输入样例】
无
【输出样例】
1:0,0->2,1->4,2->3,4->4,6->2,7->4,8
2:0,0->2,1->4,2->3,4->1,5->3,6->4,8
3:0,0->2,1->4,2->3,4->1,5->2,7->4,8
4:0,0->2,1->4,2->2,3->4,4->3,6->4,8
5:0,0->2,1->4,2->2,3->4,4->2,5->4,6->2,7->4,8
6:0,0->2,1->4,2->2,3->4,4->2,5->0,6->2,7->4,8
7:0,0->2,1->4,2->2,3->3,5->2,7->4,8
8:0,0->2,1->4,2->2,3->1,5->3,6->4,8
9:0,0->2,1->4,2->2,3->1,5->2,7->4,8
10:0,0->2,1->4,2->2,3->0,4->2,5->4,6->2,7->4,8
11:0,0->2,1->4,2->2,3->0,4->2,5->0,6->2,7->4,8
12:0,0->2,1->3,3->2,5->4,6->2,7->4,8
13:0,0->2,1->3,3->2,5->0,6->2,7->4,8
14:0,0->2,1->3,3->1,4->3,5->2,7->4,8
15:0,0->2,1->3,3->1,4->0,6->2,7->4,8
16:0,0->2,1->1,3->3,4->4,6->2,7->4,8
17:0,0->2,1->1,3->3,4->1,5->3,6->4,8
18:0,0->2,1->1,3->3,4->1,5->2,7->4,8
19:0,0->2,1->1,3->2,5->4,6->2,7->4,8
20:0,0->2,1->1,3->2,5->0,6->2,7->4,8
21:0,0->2,1->0,2->2,3->4,4->3,6->4,8
22:0,0->2,1->0,2->2,3->4,4->2,5->4,6->2,7->4,8
23:0,0->2,1->0,2->2,3->4,4->2,5->0,6->2,7->4,8
24:0,0->2,1->0,2->2,3->3,5->2,7->4,8
25:0,0->2,1->0,2->2,3->1,5->3,6->4,8
26:0,0->2,1->0,2->2,3->1,5->2,7->4,8
27:0,0->2,1->0,2->2,3->0,4->2,5->4,6->2,7->4,8
28:0,0->2,1->0,2->2,3->0,4->2,5->0,6->2,7->4,8
29:0,0->2,1->0,2->1,4->3,5->2,7->4,8
30:0,0->2,1->0,2->1,4->0,6->2,7->4,8
31:0,0->1,2->3,3->2,5->4,6->2,7->4,8
32:0,0->1,2->3,3->2,5->0,6->2,7->4,8
33:0,0->1,2->3,3->1,4->3,5->2,7->4,8
34:0,0->1,2->3,3->1,4->0,6->2,7->4,8
35:0,0->1,2->2,4->3,6->4,8
36:0,0->1,2->0,4->2,5->4,6->2,7->4,8
37:0,0->1,2->0,4->2,5->0,6->2,7->4,8【数据范围】
左下角坐标 (0, 0) 、右上角坐标 (4, 8) 。
【算法分析】
● dfs 算法通常表现为复杂的递归函数形式，因此掌握“递归”是理解 dfs 算法的基础。
● dfs 算法的常用模板，如下所示。
void dfs(int step) {判断边界 {输出解}尝试每一种可能 {满足check条件{标记继续下一步：dfs(step+1)恢复初始状态（回溯的时候要用到）}}
}【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=50;
int dx[]= {2,1,-1,-2},dy[]= {1,2,2,1};
int p[N][2]; //p[i][.] is i-th point's coord
int st[N][N];
int step;
int n,m;void print(int cnt) { //info of cnt pointsstep++;cout<<step<<":";for(int i=1; i<=cnt; i++) {cout<<p[i][0]<<","<<p[i][1];if(i!=cnt) cout<<"->";else cout<<endl;} //the cnt-th point's coord
}void dfs(int x,int y,int cnt) {p[cnt][0]=x, p[cnt][1]=y;if(x==4 && y==8) { //coord of destinationprint(cnt);return;}int tx,ty;for(int i=0; i<4; i++) {tx=x+dx[i];ty=y+dy[i];if(tx>=0 && tx<=4 && ty>=0 && ty<=8 && st[tx][ty]==0) {st[tx][ty]=1;dfs(tx,ty,cnt+1);st[tx][ty]=0;}}
}int main() {dfs(0,0,1);return 0;
}
【参考文献】