本文主要是介绍东方博宜OJ 【提高】马的遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
中国象棋半张棋盘如图（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
输入
无
输出
按要求输出路径
思路：深搜，从0,0点出发，按题目要求尝试四个方向，哪个方向能去就将坐标存入结果数组。
注意：本题0,0点在左下角，向上x会变小。
解法一：将当前点的坐标x,y传入递归函数，利用当前坐标x,y的值计算可能跳转到的4个坐标值。
#include <bits/stdc++.h>
using namespace std;
//a存储所有的路径，c存储路径数量
int a[100][3],c=0;
//四种移动规则
int fx[5]= {0,2,1,-1,-2},fy[5]= {0,1,2,2,1};//输出结果
void print(int k) {c++;cout<<c<<":";//最后一个点在循环结束打印 for(int i=1; i<k; i++) {cout<<a[i][1]<<","<<a[i][2]<<"->";}cout<<"4,8"<<endl;
}//深搜找所有路径
void dfs(int x,int y,int k) {a[k][1] = x;a[k][2] = y;if(x == 4 && y == 8){print(k);//到了终点不需要继续递归，开始后退尝试其他路径return; }int tx,ty;//往4个方向跳for (int i=1; i<=4; i++) {//跳的新点，从上当前点开始加上方向值的变化，得到4个新点 tx = x+fx[i];ty = y+fy[i];//判断马不越界if (tx>=0&&tx<=4&&ty>=0&&ty<=8) {dfs(tx,ty,k+1);}}
}int main() {//从0,0点开始递归，存入数组的下标为1的那行 dfs(0,0,1);
}这篇关于东方博宜OJ 【提高】马的遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
