迷宫问题求解——数据结构C语言的栈算法实现

你的名字 2023-06-16 08:25 79阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define Status int
    
    char a[10][10]={ 
    			{ '0','0','0','0','0','0','0','0','0','0'},  
    			{ '0','1','1','0','1','1','1','0','1','0'},
    			{ '0','1','1','0','1','1','1','0','1','0'},
    			{ '0','1','1','1','1','0','0','1','1','0'},
    			{ '0','1','0','0','0','1','1','1','1','0'},
    			{ '0','1','1','1','0','1','1','1','1','0'},
    			{ '0','1','0','1','1','1','0','1','1','0'},
    			{ '0','1','0','0','0','1','0','0','1','0'},
    			{ '0','0','1','1','1','1','1','1','1','0'},
    			{ '0','0','0','0','0','0','0','0','0','0'}
    			};
    
    //位置类型
    typedef struct
    { 
    	int row;//行
    	int col;//列
    }PosType;
    
    //栈元素类型
    typedef struct
    { 
    	int ord;//通道块在该路径上的序号
    	PosType seat;//通道块在迷宫中的坐标位置
    	int di;//从此通道块走向下一通道块的方向
    }SElemType;
    
    //指向栈元素类型的指针
    typedef struct LNode
    { 
    	SElemType data;
    	LNode *next;
    }LNode,*LinkStack;
    
    //构造空栈
    Status InitStack(LinkStack &S)
    { 
    	if(!S)
    	{ 
    		S = (LinkStack)malloc(sizeof(SElemType));
    		S->next = NULL;
    		return 1;
    	}
    	else
    		return 0;
    }
    
    //若栈不空，删除元素，用e返回其值
    Status Pop(LinkStack &S,SElemType &e)
    { 
    	LNode *p=S,*q;
    	if(!p->next)//栈为空
    	{ 
    		return 0;
    	}
    	q = p->next;
    	p->next = q->next;
    	e = q->data;
    	free(q);
    	return 1;
    
    }
    
    //插入新的栈顶元素
    Status Push(LinkStack &S,SElemType e)
    { 
    	LNode *p=S,*q;
    	if(!p)
    		return 0;
    	q = (LinkStack)malloc(sizeof(LNode));//定义s的类型，新建一个节点
    	q->data = e;
    	q->next = p->next;
    	p->next = q;
    	return 1;
    }
    
    //判断当前位置是否可以通过
    Status Pass(PosType e)
    { 
    	if(a[e.row][e.col]=='1')
    		return 1;
    	else
    		return 0;
    }
    
    //记录可以通过的路径，避免走回头路
    void Footprint(PosType e)
    { 
    	a[e.row][e.col] = 'X';
    }
    
    //继续走下一步
    PosType Nextpos(PosType curpos,int x)
    { 
    	if(x==1)
    		curpos.col=curpos.col+1;//规定向东
    	else if(x==2)
    		curpos.row= curpos.row+1;//规定向南
    	else if(x==3)
    		curpos.col= curpos.col-1;//规定向西
    	else
    		curpos.row= curpos.row-1;//规定向北
    	return curpos;
    }
    
    //不能通过的留下标记
    void Markprint(PosType e)
    { 
    	a[e.row][e.col] = '@';
    }
    
    //判断栈是否为空
    Status StackEmpty(LinkStack &S)
    { 
    	if(S->next==NULL)
    		return 1;
    	else
    		return 0;
    }
    
    //开始迷宫找路径
    void MazePath(PosType start,PosType end)
    { 
    	LinkStack S = NULL;
    	InitStack(S);
    	SElemType e;
    	PosType curpos;//定义当前位置
    	int curstep=1;//记录路径序号
    	curpos = start;
    	do{ 
    		if(Pass(curpos))//当前位置可以通过
    		{ 
    			Footprint(curpos);//留下足迹
    			e.ord = curstep;//记录该位置路径序号
    			e.seat = curpos;//记录该位置坐标
    			e.di = 1;//以东为初始方向
    			Push(S,e);
    			if(curpos.row == end.row && curpos.col == end.col)
    				break;
    			curpos = Nextpos(curpos,1);//下一个位置是当前位置的东邻,
    			curstep++;//探索下一步，记录路径序号
    		}
    		else//当前位置不能通过
    		{ 
    			if(!StackEmpty(S))
    			{ 
    				Pop(S,e);//将上一if语句放入栈顶的元素提取出来，判断其方向是否已全部走完
    				while(e.di==4 && !StackEmpty(S))
    				{ 
    					Markprint(e.seat);//留下不能通过的标记
    					Pop(S,e);//退回一步,提取新的栈顶元素判断是否还存在其他方向，直到找到新的路径为止
    				}
    				if(e.di<4)
    				{ 
    					e.di++;
    					Push(S,e);
    					curpos = Nextpos(e.seat,e.di);
    				}
    			}
    		}
    	}while(!StackEmpty(S));
    }
    
    
    void main()
    { 
    	int i,j;
    	PosType start,end;//定义入口位置和出口位置
    	start.row = 1;
    	start.col = 1;
    	end.row = 8;
    	end.col = 8;
    	printf("创建迷宫！\n");
    	for(i=0;i<10;i++)
    	{ 
    		for(j=0;j<10;j++)
    			printf("%4c",a[i][j]);
    		printf("\n");
    	}
    	MazePath(start,end);
    	printf("出口路线为:\n");
    	for(i=0;i<10;i++)
    	{ 
    		for(j=0;j<10;j++)
    			printf("%4c",a[i][j]);
    		printf("\n");
    	}
    }