递归求解迷宫问题

        相信大家伙看见过很多有关迷宫问题的文章了，但是许多文章的迷宫查找方向是上下左右。今天，小编就给大家伙来点不一样的，咱使用八个方向来查找迷宫的通路，即上、上右、右、右下、下、下左、左、左上这八个方向。下面就让小编给大家一一讲解吧。

一、问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1，1）到出口（m,n）的通路，或得出没有通路的结论。每次查找到迷宫通路后我们都会有链式输出与方阵输出两种选择。

二、模块设计：（1）迷宫建立模块，用来建立迷宫；（2）栈模块，包含栈的初始化、出栈、入栈与free栈函数，用于栈的相关操作；（3）迷宫查找模块，是主要函数，用来查找迷宫的通路；（4）迷宫输出模块，包含迷宫的链式输出与迷宫的方阵输出。

三、主要函数算法剖析：（1）判断是否到达迷宫的终点，如到达迷宫的终点就选择自己喜欢的形式输出，否则就按照定义的八个方向一次查找；

（2）先确定下一次的查找方向，再判断本次所在位置是否能够通过、是否符合迷宫规定，如不通过就换个方向查找，否则就执行下面程序；

（3）将本次所在位置标记1，表示已经查找过了，再将本次位置入栈，然后再次调用迷宫查找函数；

（4）待再次调用查找函数结束后，就将上次标记过的位置重新标记为0，后再出栈。

四、项目文件：

（1）labyrinth.h文件

#include<stdio.h>
#include<stdlib.h>

//定义迷宫的最大的大小
#define max_x 1000
#define max_y 1000
int flag;//用来记录迷宫拥有的路径
int m,n;//用来表示迷宫的行与列
struct int_slink_stack *re;//用来储存迷宫出路的栈

struct int_slink_stack//栈的定义
{    
	struct int_slink_stack_node  *top;
	int count;     
};
struct int_slink_stack_node//栈内元素的定义
{    
	int i;//本次行位置
	int j;//本次列位置
	struct int_slink_stack_node *next;
};

struct int_slink_stack *int_slink_stack_init();//栈的初始化

void int_slink_stack_free(struct int_slink_stack *s);//free栈

void int_slink_stack_push(struct int_slink_stack *s, int i,int j);//入栈函数

struct int_slink_stack_node* int_slink_stack_pop(struct int_slink_stack *s);//出栈函数

void output();//栈的链式输出

void search(int hang, int lie);//迷宫路径的查找函数

void found();//迷宫的建立并且输出函数

void map();//迷宫通路的图形输出

void xuanze();//选择迷宫路径的输出形式

（2）main.c文件

#include"labyrinth.h"

extern int a1[max_x][max_y];//定义一个储存迷宫路径的二维数组
extern int a[max_x][max_y];//定义一个储存迷宫的二维数组

void  main()
{
		re = int_slink_stack_init();//定义迷宫路径储存栈
		//输入实际迷宫的大小
		printf("请输入迷宫行(m)列(n)大小:\n");
		scanf("%d %d",&m,&n);
		//判断输入是否合理
		if(m > max_x || n > max_y || m < 1 || n < 1){//不合理
			printf("输入错误！\n");
		}else{//合理
			found();//建立迷宫，初始化迷宫
			//分别判断(1,2)、(2,1)、(2,2)和(m-1,n)(m,n-1)(m-1,n-1)是否为1
			if((a[1][2]==1 && a[2][1]==1 && a[2][2])==1 || (a[m-1][n]==1 && a[m][n-1]==1 && a[m-1][n-1]==1)){
				flag = 0;//都为1表示直接找不到迷宫的通路
			}else{//否则就先将迷宫的起点标记为1，再查找迷宫的通路
				a1[1][1]=1;	
				search(1,1);
			}
			//判断迷宫是否有通路
			if(flag == 0){//没有通路
				printf("本迷宫没有从起点到终点的路！\n");
			}else{//有通路
				printf("该迷宫一共有 %d 条路\n",flag);
			}
		}

		int_slink_stack_free(re);//free栈
}

（3）labyrinth.c文件

#include"labyrinth.h"
#include<stdlib.h>
#include<time.h>

int a[max_x][max_y];//定义一个储存迷宫的二维数组
int a1[max_x][max_y] = {0};//定义一个储存迷宫路径的二维数组
int yidong1[8][2]={
   {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};//迷宫查找的八个方向
int biao = 0;//用来辅助迷宫路径的输出,0表示可以自由输入选择

struct int_slink_stack *int_slink_stack_init()
{//栈的初始化函数
	 struct int_slink_stack *s=NULL;
	 s=(struct int_slink_stack *)malloc(sizeof(struct int_slink_stack)); 
	 s->top = NULL;
	 s->count = 0;
	 return(s) ;
}

void int_slink_stack_free(struct int_slink_stack *s)
{//free栈函数 
	struct int_slink_stack_node *p;
	while(s->top){
		p = s->top;
		s->top = p->next;
		free(p);
		s->count--;
	}
	free(s);
}

void int_slink_stack_push(struct int_slink_stack *s, int i,int j)
{//入栈函数    
	  struct int_slink_stack_node *p;
	  p=(struct int_slink_stack_node *)malloc(sizeof(struct int_slink_stack_node));
	  p->i = i;
	  p->j = j;
	  p->next = s->top;
	  s->top = p;
	  s->count++;
}

struct int_slink_stack_node* int_slink_stack_pop(struct int_slink_stack *s)
{ //出栈函数   
	struct int_slink_stack_node *p = NULL;
	p = s->top;
	s->top = p->next;
	s->count--;
	 
	return p;
}

void output()
{//迷宫路径的链式二元组输出
	int count = re->count;
	struct int_slink_stack_node *q= re->top;
	printf("迷宫的链式输出如下：\n");
	while(count > 0){
		int i = 0;
		struct int_slink_stack_node *p = q;
		while(i < count -1){
			p = p->next;
			i++;
		}
		printf("(%d %d)->",p->i,p->j);
		count--;
	}
	printf("终点\n");
}

void xuanze()
{//选择迷宫路径的输出方式
	int mn;
	printf("\n已找到第 %d 条迷宫的出路:",flag);
	//判断是否需要输入选择
	if(biao == 0){//需要选择
		printf("迷宫通路表示方法有以下几种：\n");
		printf("              1:本次迷宫通路链式表示.                      \n");
		printf("              2:本次迷宫通路图形表示.                      \n");
		printf("              3:迷宫通路就以图形表示.                      \n");
		printf("              其他:迷宫通路就以链式表示.                    \n");
		printf("请输入您的选择:");
		scanf("%d",&mn);
	}else{//不需要选择
		mn = biao;
	}
	switch(mn){
		case 1: output();biao = 0;//本次迷宫路径链式输出
			break;
		case 2: map();biao = 0;//本次迷宫路径图形输出
			break;
		case 3: map();biao = 3;//迷宫路径一直以图形输出
			break;
		default: output();biao = 5;//迷宫路径一直以链式输出
	}
}

void found()
{//建立迷宫并且输出函数
	int i,j;
	srand((unsigned int)time(0));//定义随机数种子
	//建立迷宫的墙
	for(i=0;i<=m+1;i++){
        a[i][0]=2;
        a[i][n+1]=2;
		a1[i][0]=2;
        a1[i][n+1]=2;
    }
	for(i=0;i<=n+1;i++){
        a[0][i]=2;
        a[m+1][i]=2;
		a1[0][i]=2;
        a1[m+1][i]=2;
    }
	//建立实际迷宫
 	for(i=1;i<=m;i++){
    	for(j=1;j<=n;j++){
				a[i][j] = rand()%2;
			}
	}
	//将迷宫的起点与终点强制置0
	a[1][1] = 0;a[m][n] = 0;
	//输出随机生成的迷宫
	printf("随机生成的迷宫为(2代表迷宫边界)：\n");
	for(i=0;i<m+2;i++){
    	for(j=0;j<n+2;j++){
         printf("%d ",a[i][j]);
		}
		printf("\n");
	}
}

void map()
{//迷宫的图形输出
	int i,j;
	int count = re->count;//获取栈内元素的个数大小
	struct int_slink_stack_node *q= re->top;//获取栈内元素的栈顶指针
	a1[m][n] = 1;//强制将迷宫终点置1
	//图形输出迷宫
	printf("迷宫的通路地图如下(0表示墙，1代表通路,2代表边界):\n");
	for(i = 0;i < m+2;i++){
		for(j = 0;j < n+2;j++){
			printf("%d ",a1[i][j]);
		}
		printf("\n");
	}
	//图形输出迷宫路径后还需要出栈
	while(count > 0){
		q = q->next;
		count--;
	}
}

void search(int hang, int lie)
{//迷宫通路查找函数
    int i,x,y;
	//判断是否到达迷宫的终点
	if(hang==m && lie==n ){//到达迷宫终点直接输出
		flag += 1;
		xuanze();
		return ;
	}else{//未到达迷宫终点继续查找
		for(i=0;i<8;i++){//按照定义的八个方向一次查找
				//求得下一次查找的位置
				x=hang + yidong1[i][0];
				y=lie + yidong1[i][1];
				//判断下一次查找是否为0,是否在合理的范围内
				if(a1[x][y]||a[x][y]||x<1||y<1||x > m||y > n)  continue;//下一次查找不符合要求就再次查找
				//复合查找要求
				a1[x][y]=1;//将本次所在位置标记1，表示已经查找过了
				int_slink_stack_push(re,hang,lie);//将本次位置入栈
				search(x,y);//查找下一次位置
				a1[x][y]=0;//将本次所在位置标记0，表示未查找
				int_slink_stack_pop(re);//出栈
			}
	}
}

五、程序执行结果：

待输入选择：

选项1：

选项2：

（注：至于其他的两个选项其实就是对于选项1、选项2的另外一种选择形式。）

相信大家看了我的文章或多或或少有一些关于迷宫问题求解的思路。小编第一次写文章，倘若有啥不妥之处欢迎大家留言。若大家在看完之后有什么疑惑，也欢迎大家留言。