1337: 【作】【提高】马的遍历
内存限制：16 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
中国象棋半张棋盘如图（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
输入
无
输出
按要求输出路径
样例输入 复制
样例输出 复制
提示
#include <bits/stdc++.h>
using namespace std;
int a[100][100],t=0; //路径总数和路径
int dx[4]={2,1,-1,-2},dy[4]={1,2,2,1}; //四种移动规则
void print(int n) //输出结果
{
t++;
cout<<t<<":";
for(int i=1;i<n;i++){
cout<<a[i][1]<<","<<a[i][2]<<"->";
}
cout<<"4,8"<<endl;
}
void dfs(int k) //递归回溯
{
for (int i=0;i<=3;i++){ //往4个方向跳
int tx=a[k-1][1]+dx[i],ty=a[k-1][2]+dy[i];
if (tx>=0&&tx<=4 &&ty>=0&&ty<=8){ //判断马不越界
a[k][1]=tx; //保存当前马的位置
a[k][2]=ty;
if (tx==4&&ty==8){
print(k);
}else{
dfs(k+1); //搜索下一步
}
}
}
}
int main(){
a[1][1]=0;
a[1][2]=0;
dfs(2); //从坐标(0,0)开始往右跳第二步
}