C语言实现迷宫问题（超级详细）

古城微笑少年丶 2023-07-18 02:19 19阅读 0赞

# C语言实现迷宫问题 #

利用栈和递归的思想很容易实现，代码在下面，不懂就问。

#include<stdio.h>
    #include<stdlib.h>
    #define m 6  
    #define n 8 
    #define STACK_INIT_SIZE 100 
    typedef struct
    {
    	int x,y;
    }SElemType;
    
    typedef struct
    {
    	SElemType stack[STACK_INIT_SIZE];
    	int top;
    }SqStack;
    
    typedef struct
    {
    	int x,y;
    }Item;
    
    int maze[m+2][n+2]=
    {
    	  /*0,1,2,3,4,5,6,7,8,9*/
    /*0*/  {1,1,1,1,1,1,1,1,1,1},
    /*1*/  {1,0,1,1,1,0,1,1,1,1},
    /*2*/  {1,1,0,1,0,1,1,1,1,1},
    /*3*/  {1,0,1,0,0,0,0,0,1,1},
    /*4*/  {1,0,1,1,1,0,1,1,1,1},
    /*5*/  {1,1,0,0,1,1,0,0,0,1},
    /*6*/  {1,0,1,1,0,0,1,1,0,1},
    /*7*/  {1,1,1,1,1,1,1,1,1,1},
    };
    int t[m+2][n+2]={0};  //与迷宫相同的二维数组，用来表示该条路有没有走；
    Item Move[8]=       //记录走的方向；
    {
    	{0,1},{1,1},{1,0},{1,-1},
                  {0,-1},{-1,-1},{-1,0},{-1,1}
    };
    
    int sum=0;  //记录有几条路径 
    
    
    //打印路径 
    void Print(int sum,SqStack a)
    {
    	int i;
    	printf("迷宫的第%d条路径如下:\n",sum);
    	for(i=0;i<=a.top;i++)
    		printf("(%d,%d)->",a.stack[i].x,a.stack[i].y);
    	printf("出口\n\n");
    	printf("\n");
    }
     
     
    //符合规则的压入栈 
    void Push_SqStack(SqStack *s,SElemType x)
    {
    	if(s->top==STACK_INIT_SIZE-1)
    		printf("\n栈满!");
    	else
    	{
    		s->top++;
    		s->stack[s->top]=x;
    	}	
    }
    
    
    //检查栈是否为空 
    int Empty_SqStack(SqStack *s)
    {
    	if(s->top==-1)
    		return 1;
    	else 
    		return 0;
    } 
    
    
    //删除栈顶的元素，退后操作 
    void Pop_SqStack(SqStack *s)
    {
    	if(Empty_SqStack(s))
    	{
    		printf("\n栈空!");
    		exit(0);
    	}
    	else
    	{
    		s->top--;
    	}
    }
    
    
    void path(int x,int y,SqStack elem)
    {
    	int i,a,b;
    	SElemType temp;
    	if(x==6&&y==8)
    	{
    		sum++;
    		Print(sum,elem);
    	}
    	else
    	{
    		for(i=0;i<8;i++)          //遍历八个方向
    		{
    			a=x+Move[i].x;      
    			b=y+Move[i].y;      
    			if(!maze[a][b]&&!t[a][b])   
    			{
    				temp.x=a;temp.y=b;
    				t[a][b]=maze[a][b]=1;     //用数组t,M记录这个位置已经走过了 
    				Push_SqStack(&elem,temp);  
    				path(a,b,elem);        
    				t[a][b]=maze[a][b]=0;     //回溯之后需要将这个位置清空，表示这条路没有走过
    				Pop_SqStack(&elem);		  
    			}
    		}
    	}
    }
    
     
    
    int main()
    {
    	SqStack *s;
    	s=(SqStack *)malloc(sizeof(SqStack));
    	s->stack[0].x=1;     
    	s->stack[0].y=1;
    	s->top=0;             
    	t[1][1]=maze[1][1]=1; 
    	path(1,1,*s);
    	return 0;
    }

***Only if we work harder than others can we achieve ourselves***