mazepath.cpp

本程序实现某一已知迷宫的路径搜索

#include <stdio.h>
#include <stdlib.h>
#define M  6  //迷宫的行数
#define N  6  //迷宫的列数
//0--通道；1--墙；2--入口；3--出口。                              图3.4 迷宫
int maze[M][N] = { 1,2,1,1,1,1,  1,0,1,0,0,1,  1,0,0,0,0,1,
				1,1,0,0,1,1,  1,0,1,0,0,1,  1,1,1,1,3,1 };
typedef struct list{//定义链表结构 ,利用双向链作为栈
	int m,  n;//行、列号表示位置
	struct list *next;  //指向下一个节点
	struct list *back;  //指向前一个节点
}node,*pointer;  //定义节点  //定义动态指针
bool  pass[M][N];  //记录迷宫中各个位置是否走过
int m,n;//  m,n代表当前位置
pointer ptr,preptr,first;  //动态指针，分别代表目前结点、上一个结点与第一个结点

void Start()  //搜寻入口
{
    int i,j;
	for(i=0;i<M-1;i++){
		for(j=0;j<N-1;j++)
			if(maze[i][j]==2)  break;
		if(maze[i][j]==2)  break;
	}
	m = i;  n = j;
	ptr = (pointer)malloc(sizeof(node));
	ptr->m = m;  ptr->n = n;
	ptr->next = NULL;  ptr->back = NULL;
	first = ptr;
}
void  Search ()  //搜寻出口
{
do{
	if(maze[m+1][n]==1 || pass[m+1][n])    //下一格是墙或下一格走过
		if(maze[m][n+1] == 1 || pass[m][n+1])     //右一格是墙或右一格走过
			if(maze[m][n-1] ==1 || pass[m][n-1])   //左一格是墙或左一格走过
				if(maze[m-1][n] == 1 || pass[m-1][n])   //上一格是墙或上一格走过
				{
					if(ptr->back != NULL){
						ptr = ptr->back;  free(ptr->next);  ptr->next = NULL;
					}
					m = ptr->m;  n = ptr->n;
				}
				else {
						m-=1;    //往上一格
						ptr->next = (pointer)malloc(sizeof(node));
						ptr->next->m = m;  ptr->next->n = n;
						preptr = ptr;  ptr->next->next = NULL;
						pass[m][n] = true;  ptr = ptr->next;  ptr->back = preptr;
					}
			else
			{
				n-=1;    //往左一格
				ptr->next = (pointer)malloc(sizeof(node));
				ptr->next->m = m;  ptr->next->n = n;
				preptr = ptr;  ptr->next->next = NULL;
				pass[m][n] = true;  ptr = ptr->next;  ptr->back = preptr;
			}
	    else
		{
			n+=1;    //往右一格
			ptr->next = (pointer)malloc(sizeof(node));
			ptr->next->m = m;  ptr->next->n = n;
			preptr = ptr;  ptr->next->next = NULL;
			pass[m][n] = true;  ptr = ptr->next;  ptr->back = preptr;
		}
	else
	{
		m+=1;    //往下一格
		ptr->next = (pointer)malloc(sizeof(node));
		ptr->next->m = m;  ptr->next->n = n;
		preptr = ptr;  ptr->next->next = NULL;
		pass[m][n] = true;  ptr = ptr->next;  ptr->back = preptr;
	}
}while((maze[m][n] != 3) && (ptr->back != NULL)); 
if(ptr->back == NULL)
	printf("%s\n","找不到迷宫出口,无出口!");
if(maze[m][n] == 3)
	printf("%s%d,%d\n","找到迷宫出口--",m,n);
pointer p=first;
while(p){//输出路径
		printf("%d, %d\n",p->m,p->n);
		p=p->next;
	}
}
void main(){
Start();
Search();
}