目录

搜索与回溯基本框架 

基本框架一

基本框架二

实战导入

 算法分析

搜索策略

代码示例

输出结果

小结 

---

本文我们来讲C++知识精讲的第2篇，马的遍历，此专栏会讲许多，各种各样的类型，如果喜欢此专栏请订阅持续关注，感谢大家的支持。接下来，进入今天的知识精讲。

搜索与回溯基本框架 

基本框架一

int search(int k)
{
	for(i=1;i<=算符种数;i++)
	if(满足条件)
	{
        保存结果
        if(到达目的地)输出解；
        else search(k+1);
        恢复：保存结果之前的状态｛回溯一步｝
	}
}

基本框架二

int search(int k)
{
	if(到达目的地)输出解；
	else
	for(i=1;i<=算符种数;i++)
	if(满足条件)
	{
        保存结果
        search(k+1);
        恢复：保存结果之前的状态｛回溯一步｝
	}
}

实战导入

中国象棋半张棋盘如图a所示。马自左下角向右上角跳。今规定只许往右跳，不许往左跳。比如图a所示为一种跳行路线，并将所经过路线打印出来。打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8……

 算法分析

如图b，马最多有四个方向，若原来的横坐标为j，纵坐标为i，则四个方向的移动可表示为：

1：（i,j）->(i+2,j+1);(i<3,j<8)

2：（i,j）->(i+1,j+2);(i<4,j<7)

3：（i,j）->(i-1,j+2);(i>0,j<7)

4：（i,j）->(i-2,j+1);(i>1,j<8)

搜索策略

S1：A[1]:=(0,0);

S2:从A[1]出发，按移动规则依次选定某个方向，如果到达的是（4，8），则转向S3，否则继续搜索下一个到达的顶点；

S3：打印路径。

代码示例

#include
using namespace std;
int a[100][3],t=0;//路径总数和路径
int x[4]={2,1,-1,-2},//四种移动规则
	y[4]={1,2,2,1};
int search(int);//搜索
int print(int);//打印
int main()//主程序
{
	a[1][1]=0;a[1][2]=0;//从坐标（0，0）开始往右跳第二步
	search(2);
};
int search(int i){
	for(int j=0;j<=3;j++)//往四个方向跳
	if(a[i-1][1]+x[j]>=0&&a[i-1][1]+x[j]<=4&&a[i-1][2]+y[j]>=0&&a[i-1][2]+y[j]<=8){//判断马不越界
	a[i][1]=a[i-1][1]+x[j];//保存当前马的位置
	a[i][2]=a[i-1][2]+y[j];
	if(a[i][1]==4&&a[i][2]==8)print(i);
	else search(i+1);//搜索下一步
	 }
}
int print(int ii){
	t++;
	cout< 
输出结果 
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
 
小结  
 搜索与回溯经典之马的遍历讲完了，希望能帮助到大家，如有建议欢迎提出。