数据结构8————栈的应用2-非递归解决迷宫和马踏棋盘问题_马踏棋盘问题 非递归

数据结构8————非递归解决迷宫和马踏棋盘问题

一.前言

1. 迷宫问题的描述

在高为H，宽为W的地图中，0代表可以走，1代表障碍物，不重复的走到终点。给定地图和终点求下列问题

• 子问题1 按照右下左上（优先级）输出一条到达终点路径
• 子问题2 输出所有路径

2. 马踏棋盘问题的描述

将马放在国际象棋8×8棋盘某个方格中，马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线将数字1,2，…，64依次填入一个8×8的方阵并输出。

• 子问题1 按照顺时针的（优先级）输出一条踏完所有方格的路径(深搜)
• 子问题2 输出一条踏完所有方格的的路径（贪心）
• 子问题3 输出所有走法（深搜）
• 子问题4 输出指定数量的走法(贪心)

3.使用的算法

• 数据结构：栈
• 算法：深度优先搜索,贪心优化

4.其他

• 所有贴出的代码，只贴了核心部分，其他部分(头文件.栈的运算)都没有贴出来
• 完整代码可在文末的git中下载。

二.迷宫 子问题1

1.思路

• 总思路：按着k=0~4四个方向依次试探，将可走的点入栈，入栈后继续试探新的点的四个方向，当4个方向都不可走时出栈（回溯），出栈后接着出栈前的方向继续试探（防止重复）
• 四个方向的试探顺序：右下左上。
• e1代表当前决定是否要入栈的元素（待入栈），e1的结构体组成(e1坐标+e1到e2的方向k)
• e2代表e1本次试探方向的棋盘坐标
• e1入栈的时机
  • 如果存在一个方向使e2既未出界也没用被走过，那么入栈e1
  • 此时原e2变成了新的e1(待入栈)，然后试探此时e1的0~4四个方向的e2。
  • 步数+1，标记已走
• 出栈的时机(回溯)
  • 如果e1的四个方向都无法走，那么将栈内元素出栈
  • 此时出栈的元素变成了新e1(待入栈)，然后继续接着入栈前的方向试探(不是从0方向开始)；
  • 步数-1，取消标记
• 循环的终止条件
  • 如果此时e1==终点坐标，结束循环，输出路径

2.难点

• 入栈的时机
• 出栈的时机
• 回溯时接着入栈前的方向继续试探(实现方法：e1元素内保存e1->e2的方向回溯后，e1接着原方向继续试探)。

3.代码

数据结构定义和预定义的数据

#define MAXSIZE 20
#define TRUE 1
#define FALSE 0 
#define W 4 //迷宫的高和宽 
#define H 5 
typedef struct{//栈内要存的元素
	int x;
	int y;
	int direction;
} Elemtype;

SeqStack *SS;//栈
int book[H][W];//标记数组
int n=3,m=3;//终点坐标 
int a[H][W]={{0,0,1,0}, //地图 
			 {0,0,0,0},
		         {0,0,1,1},
			 {0,1,0,0},
			 {0,0,0,0}};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

核心代码

int dfs(Elemtype e){
	int k;
	int next[4][2]={{0,1},//右 
	                {1,0},//下 
			{0,-1},//左 
	                {-1,0}};//上
	Elemtype e1,e2;    //e1：待入栈，e2：e1的试探方向的坐标 
	e1 = e;
	e1.direction=0;
	while(e1.x!=n||e1.y!=m){ // m n终点坐标 
			
		for(k=e1.direction;k<4;k++){
			
			e2.x=e1.x+next[k][0];//下一步 
			e2.y=e1.y+next[k][1];
			e1.direction=k;
			if(e2.x<0||e2.y<0||e2.y>=W||e2.x>=H)//判断是否越界 
				continue;
				
			if(a[e2.x][e2.y]!=1&&book[e2.x][e2.y]==0)//判断下一步是否被走过和是否有障碍物
			{
				Push(SS,e1);
				book[e1.x][e1.y]=1;//标记
				e1=e2; 
				e1.direction=0;
				//printf("入(%d,%d)%d\n",e1.x,e1.y,e1.direction);
				break;				
			} 
		}
		
		if(k==4){
			Pop(SS,&e1); 
			book[e1.x][e1.y]=0;
			//printf("出(%d,%d)%d\n",e1.x,e1.y,e1.direction); 
			e1.direction++;
		}
	}
	
	Push(SS,e1);
	book[e1.x][e1.y]=1;
	
	int i;
	if(e1.x==n&&e1.y==m){
		for(i=0;i<SS->top+1;i++){
			printf("过程(%d,%d)方向:%d\n",SS->data[i].x,SS->data[i].y,SS->data[i].direction); 
		}
	}
}
int main(void)
{
	Elemtype e;
	SS=InitStack();
	e.x=0;
	e.y=0;
	e.direction=0;
	book[0][0]=1;//标记起始点
	dfs(e);//第一个参数是起始点的x坐标，第二个参数是起始点的y坐标，第三个参数是步数 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

4.运行结果

三.迷宫 子问题2

1.思路

• 基本思路和子问题1差不多
• 区别在于:
  • 终止条件变为当前栈为空栈
  • 当到达终点时，先入栈一次，输出结果，然后出栈两次。

2.代码

数据结构定义和预定义的数据

#define MAXSIZE 20
#define TRUE 1
#define FALSE 0 
#define W 4
#define H 5
typedef struct{
	int x;
	int y;
	int direction;
} Elemtype;

SeqStack *SS;
int book[H][W];
int a[H][W]={{0,0,1,0},
             {0,0,0,0},
             {0,0,1,1},
	     {0,1,0,0},
	     {0,0,0,1}};
int n=3,m=3;//终点坐标 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

核心代码

int dfs(Elemtype e){
	int k;
	int next[4][2]={{0,1},//右 
	                {1,0},//下 
			        {0,-1},//左 
	                {-1,0}};//上
	Elemtype e1,e2;
	e1 = e;
	e1.direction=0;
	do{	
			
		for(k=e1.direction;k<4;k++){
			
			e2.x=e1.x+next[k][0];//下一步 
			e2.y=e1.y+next[k][1];
			e1.direction=k;
			
			if(e2.x<0||e2.y<0||e2.y>=W||e2.x>=H)//判断是否越界 
				continue;
				
			if(a[e2.x][e2.y]!=1&&book[e2.x][e2.y]==0)//判断下一步是否被走过和是否有障碍物
			{
				//入栈 
				Push(SS,e1);
				book[e1.x][e1.y]=1;//标记
				e1=e2; 
				e1.direction=0;
				//printf("入(%d,%d)%d\n",e1.x,e1.y,e1.direction);
				break;				
			} 
			
		}
		
		int i;
		//到达终点 
		if(e1.x==n&&e1.y==m){
			Push(SS,e1);
			book[e1.x][e1.y]=1;
			
			for(i=0;i<SS->top+1;i++){
				printf("过程(%d,%d)方向:%d\n",SS->data[i].x,SS->data[i].y,SS->data[i].direction); 
			}
			printf("\n\n");
			Pop(SS,&e1);
			book[e1.x][e1.y]=0;
		}
		
		if(k==4||e1.x==n&&e1.y==m){
			//出栈 
			Pop(SS,&e1);
			book[e1.x][e1.y]=0;
			//printf("出(%d,%d)%d\n",e1.x,e1.y,e1.direction); 
			e1.direction++;
		}
	}while(!StackEmpty(SS)||e1.direction!=4);
	
}
int main(void)
{
	Elemtype e;
	SS=InitStack();
	e.x=0;//起点 
	e.y=0;
	e.direction=0;
	book[0][0]=1;//标记起始点
	dfs(e);//第一个参数是起始点的x坐标，第二个参数是起始点的y坐标，第三个参数是步数 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

3.运行结果

四.马踏棋盘 子问题1

1.思路

• 总思路：按着k=0~7八个方向依次试探，将可走的点入栈，入栈后继续试探新的点的四个方向，当8个方向都不可走时出栈（回溯），出栈后接着出栈前的方向继续试探（防止重复）
• 八个方向的试探顺序：从右上开始，依次顺时针遍历。
• 和迷宫子问题1思路很像
• e1代表当前决定是否要入栈的元素（待入栈），e1的结构体组成(e1坐标+e1到e2的方向k)
• e2代表e1本次试探方向的棋盘坐标
• e1入栈的时机
  • 如果存在一个方向使e2既未出界也没用被走过，那么入栈e1
  • 此时原e2变成了新的e1(待入栈)，然后试探此时e1的0~7八个方向的e2。
  • 步数+1，标记已走
• 出栈的时机(回溯)
  • 如果e1的八个方向都无法走，那么将栈内元素出栈
  • 此时出栈的元素变成了新e1(待入栈)，然后继续接着入栈前的方向试探(不是从0方向开始)；
  • 步数-1，取消标记
• 循环的终止条件
  • 如果此时马的步数==64，结束循环，输出路径

2.代码

数据结构定义和预定义的数据

#define MAXSIZE 100
#define TRUE 1
#define FALSE 0 
#define H 8
#define W 8 
typedef struct{
	int x;
	int y;
	int direction;
} Elemtype;

int book[W][H] ={0};//标记
int next[8][2]={{-2,1}, //下一步走法 
		{-1,2}, 
		{1,2},
	        {2,1}, 
		{2,-1},
		{1,-2}, 
		{-1,-2},
	        {-2,-1}};          
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

核心代码

int dfs(Elemtype e){

	 int k,step=1;
	 Elemtype e1=e,e2;//e1：待入栈元素。e2：e1试探方向的元素 
	 e1.direction=0;
	 
	while(step!=W*H){
			
		for(k=e1.direction;k<8;k++){ //如果上一步是入栈，则e1.direction=0，如果上一步是出栈则e1.direction++ 
			
			e2.x=e1.x+next[k][0];
			e2.y=e1.y+next[k][1];
			e1.direction = k;//e1到e2的走法 
			
			if(e2.x<0||e2.x>=H||e2.y<0||e2.y>=W)
				continue;
		
			if(book[e2.x][e2.y]==0){
				book[e1.x][e1.y]=step;
				Push(SS,e1);//入栈e1 
				
				e1 = e2; //原e2变成e1(待入栈) 
				e1.direction=0;//下次试探从0开始 
				step++;
				break;
			}
		}
		if(k==8){
			Pop(SS,&e1);//出栈栈顶元素，栈顶元素称为新的e1(待入栈) 
			
		 	book[e1.x][e1.y]=0; 
			step--;
			e1.direction++;//下次试探接着入栈键的方向 
		}			
	}
	
	//标记终点元素 
	book[e1.x][e1.y]=step;
	
	int i,j;
	if(step==W*H){//打印 
		for(i=0;i<H;i++){ 
			for(j=0;j<W;j++)
				printf("%4d",book[i][j]);
		 	printf("\n");
		} 	
	}
	return ;	
}

int main(void)
{
	Elemtype e;
	
	SS=InitStack();
	printf("请输入起点坐标：\n");
	scanf("%d%d",&e.x,&e.y);
	
	int a=clock();
	dfs(e);
	int b=clock();
	printf("\n%lf秒\n",(b-a)/1000.0);
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

3.运行结果

五.马踏棋盘 子问题2

1.思路

贪心算法：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择

• 对于马踏棋盘问题而言，那个方向本次最优的，就是这个选择的可走的点（权值）少越好
• 计算权值时(Sortint函数)
  • e：马当前所在的位置
  • e1：马的八个方向
  • e2：e1可以走的方向。
  • e2数目的多少就是e1权值的大小
  • 所以e应该走e1权值最小(但是非0)方向
  • b[8]里面存将8个方向的权值(元素结构体：方向+权值)排序后的结果。
• 寻找路径时：(dfs函数)
  • 不同于子问题一按照顺时针方向遍历，按照贪婪算法的思想，应该按照权值大小进行遍历
  • 所以在遍历方向时，应该先计算e1(本次待入栈元素)八个方向的权值
  • e1入栈时机：b[k]的权值不为0，入栈后，标记，步数+1，k=0；e1更新，计算新e1的各个方向权值
  • 出栈时机：b[k]==0,出栈后，出栈元素为e1，取消标记，步数-1，k接着入栈时的大小加一，计算新e1各个方向的权值
• 循环的终止条件
  • 如果此时马的步数==64，结束循环，输出路径

2.代码

数据结构定义和预定义的数据

#define MAXSIZE 100
#define TRUE 1
#define FALSE 0 
#define W 8
#define H 8
typedef struct{ //栈内元素 
	int x;
	int y;
	int direction;
} Elemtype;
typedef struct //栈 
{
	Elemtype data[MAXSIZE];
	int top; 
}SeqStack; 

typedef struct{ //权值 
	int value;
	int direction;
}Value;

SeqStack *SS;
int book[W][H] ={0};//标记
int next[8][2]={{-2,1}, //下一步走法 
		{-1,2}, 
		{1,2},
	        {2,1}, 
		{2,-1},
		{1,-2}, 
		{-1,-2},
	        {-2,-1}};
int step=1;        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

核心代码

void Sortint(Elemtype e , Value b[8]){ //计算e点8个方向的权值，并排序 
	Elemtype e1,e2;
	int k1,k2;
	for(k1=0;k1<8;k1++){
		e1.x = e.x+next[k1][0];
		e1.y = e.y+next[k1][1];
		
		b[k1].direction=k1;
		b[k1].value=0;
		if(book[e1.x][e1.y]!=0||e1.x<0||e1.y<0||e1.x>=H||e1.y>=W)//如果这个点不能走，则跳过这个点
			continue;
		
		for(k2=0;k2<8;k2++){//计算这个点的权值 
			e2.x= e1.x+next[k2][0];
			e2.y= e1.y+next[k2][1];
			if(book[e2.x][e2.y]!=0|| e2.x<0 ||e2.y<0 ||e2.x>=H ||e2.y>=W )
				continue;
			
			 b[k1].value++;//权值加一 
		} 
	}
	//按权值大小排序(插入排序，0放末尾) 
	int i,j;
	Value t;
	for(i=1;i<8;i++){
		t=b[i];
		for(j=i-1;j!=-1&&(t.value<b[j].value||b[j].value==0)&&t.value!=0;j--)
			b[j+1]=b[j];
		b[j+1]=t;
	
	}
	return ;
}
  
int dfs(Elemtype e){

	int k;
	Value b[8];//存放8个方向权值 
	Elemtype e1=e,e2;//e1当前待入栈点，e2：e1试探方向的元素 
	int i,j;
	
	Sortint(e1,b);//计算权值 
	e1.direction=0;
	while(step!=W*H){
	
		Sortint(e1,b);//计算权值 
		k=e1.direction;
				
		if(b[k].value!=0){
			e1.direction = k;//k为当前权值的下标 
			
			//入栈 
			Push(SS,e1); 
			book[e1.x][e1.y]=step;
			step++;
			 
			//更新e1 
			e1.x = e1.x+next[b[k].direction][0];
			e1.y = e1.y+next[b[k].direction][1];
			e1.direction=0; 
		}
		if(b[k].value==0&&step!=W*H){
			//出栈 并更新e1 
			Pop(SS,&e1); 
			book[e1.x][e1.y]=0; 
			step--;
			e1.direction++;//下次试探接着入栈键的方向 
		}
		
	}
	
	//标记将终点元素入栈 
	book[e1.x][e1.y]=step;
	
	if(step==W*H){         //打印 
		for(i=0;i<H;i++){ 
			for(j=0;j<W;j++)
				printf("%4d",book[i][j]);
		 	printf("\n");
		} 
	}
		
}

int main(void)
{
	Elemtype e;
	SS=InitStack();
	printf("请输入起点坐标：\n");
	scanf("%d%d",&e.x,&e.y);
	book[e.x][e.y]=step;//标记起始点
	
	int a=clock();
	dfs(e);
	int b=clock();
	printf("\n%lf秒\n",(b-a)/1000.0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

3.运行结果

六.马踏棋盘 子问题3

1.思路

• 思路和马踏1棋盘子问题一类似
• 区别在于：
  • 终止条件变为栈为空
  • 步数变为64时，先标记，打印，取消标记，出栈。

2.代码

int dfs(Elemtype e){

	 int k,step=1;
	 int i,j;
	 Elemtype e1=e,e2;
	 e1.direction=0;
	 do{
			
		for(k=e1.direction;k<8;k++){
			
			e2.x=e1.x+next[k][0];
			e2.y=e1.y+next[k][1];
			e1.direction = k; 
			
			if(e2.x<0||e2.x>=W||e2.y<0||e2.y>=H)
				continue;
		
			if(book[e2.x][e2.y]==0){
				book[e1.x][e1.y]=step;//标记
				Push(SS,e1);
				//printf("入(%d,%d)%d %d\n",e1.x,e1.y,e1.direction,SS->top);
				e1 = e2;
				e1.direction=0;
				step++;
				break;
			}
		}	
		
		if(step==H*W){//打印 
		
			book[e1.x][e1.y]=step;
			for(i=0;i<H;i++){ 
				for(j=0;j<W;j++)
					printf("%4d",book[i][j]);
			 	printf("\n");
			} 
			t++;
			printf("第%d种走法\n",t);
			book[e1.x][e1.y]=0;
			
		}
		if(k==8||step==H*W){ 
			Pop(SS,&e1);	
			//printf("出(%d,%d)%d %d\n",e1.x,e1.y,e1.direction,SS->top);
		 	book[e1.x][e1.y]=0;
			step--;
			e1.direction++;
		}	
			
	}while(!StackEmpty(SS)||e1.direction!=8); 
		
	return ;	
}

int main(void)
{
	Elemtype e;
	SS=InitStack();
	e.x=0;
	e.y=0;
	book[0][0]=step;//标记起始点
	int a=clock();
	dfs(e);
	int b=clock();
	printf("\n%lf秒\n",(b-a)/1000.0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

3.运行结果

七.马踏棋盘 子问题4

1.思路

• 思路和马踏1棋盘子问题一类似
• 区别在于：
  • 终止条件变为当前方法数等于目标方法数
  • 步数变为64时，先标记，打印，取消标记，出栈。
  • 输出指定多方法中，Q代表的只遍历权值排名前Q的方向(提高速度)。所以，输出的结果可能不会输出全部的走法。如果要改成输出全部走法，把Q改为8.

2.代码

void Sortint(Elemtype e , Value b[8]){ //计算e点8个方向的权值，并排序 
	Elemtype e1,e2;
	int k1,k2;
	for(k1=0;k1<8;k1++){
		e1.x = e.x+next[k1][0];
		e1.y = e.y+next[k1][1];
		
		b[k1].direction=k1;
		b[k1].value=0;
		if(book[e1.x][e1.y]!=0||e1.x<0||e1.y<0||e1.x>=H||e1.y>=W)//如果这个点不能走，则跳过这个点
			continue;
		
		for(k2=0;k2<8;k2++){//计算这个点的权值 
			e2.x= e1.x+next[k2][0];
			e2.y= e1.y+next[k2][1];
			if(book[e2.x][e2.y]!=0|| e2.x<0 ||e2.y<0 ||e2.x>=H ||e2.y>=W )
				continue;
			
			 b[k1].value++;//权值加一 
		} 
	}
	//按权值大小排序(插入排序，0放末尾) 
	int i,j;
	Value t;
	for(i=1;i<8;i++){
		t=b[i];
		for(j=i-1;j!=-1&&(t.value<b[j].value||b[j].value==0)&&t.value!=0;j--)
			b[j+1]=b[j];
		b[j+1]=t;
	
	}
	return ;
}
  
int dfs(Elemtype e){

	int k;
	Value b[8];//存放8个方向权值 
	Elemtype e1=e,e2;//e1当前待入栈点，e2：e1试探方向的元素 
	int i,j;
	
	Sortint(e1,b);//计算权值 
	e1.direction=0;
	do{
	
		Sortint(e1,b);//计算权值 
		k=e1.direction;
				
		if(b[k].value!=0&&k<Q){   //只遍历权值排名前Q的方向 
			e1.direction = k;//k为当前权值的下标 
			
			//入栈 
			Push(SS,e1); 
			book[e1.x][e1.y]=step;
			step++;
			 //printf("入(%d,%d)%d %d\n",e1.x,e1.y,e1.direction,SS->top);
			//更新e1 
			e1.x = e1.x+next[b[k].direction][0];
			e1.y = e1.y+next[b[k].direction][1];
			e1.direction=0; 
		}
		
		if(step==W*H){  
			t++; 
			book[e1.x][e1.y]=step;	
	     	 //打印 
			for(i=0;i<H;i++){ 
				for(j=0;j<W;j++)
					printf("%4d",book[i][j]);
		 		printf("\n");
			} 
			printf("第%d种走法\n\n",t); 
			book[e1.x][e1.y]=0;	 
		}
		if(b[k].value==0||step==W*H||k>=Q){
			//出栈 并更新e1 
			Pop(SS,&e1);
			//printf("出(%d,%d)%d %d\n",e1.x,e1.y,e1.direction,SS->top); 
			book[e1.x][e1.y]=0; 
			step--;
			e1.direction++;//下次试探接着入栈键的方向 
		}
	}while(count!= t);  
}

int main(void)
{
	Elemtype e;
	SS=InitStack();
	printf("请输入起点坐标：\n");
	scanf("%d%d",&e.x,&e.y);
	book[e.x][e.y]=step;//标记起始点
	printf("要计算多少种走法:\n");
	scanf("%d",&count);
	int a=clock();
	dfs(e);
	int b=clock();
	printf("\n%lf秒\n",(b-a)/1000.0);
	getchar();
}
 
	            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

3.运行结果

八.对比递归，非递归，贪心优化三种算法运行时间

九.源代码

tast5