C语言——迷宫问题的非递归解法

骑猪看日落 2023-06-16 10:39 2阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    
    
    void MazeMap();
    int **InitMaze();
    int **InitBook();
    int **CreatElem(); 
    void PrintMaze(int **array);
    void FreeMaze(int **array);
    
    int m_row;
    int m_col;
    int count=1;
    
    
    
    //创建一个结构体,用来存放迷宫问题所走过的路程,x,y为坐标,direction为方向1,2,3,4为东南西北 
    typedef struct MazeStep{
    	int x;
    	int y;
    	int direction;
    	struct MazeStep *prior;
    	struct MazeStep *next;
    }MazeStep;
    
    //创建一个带头节点的循环链表,初始化 
    MazeStep *CreatMazeStep(){
    	MazeStep *pHead=(MazeStep *)malloc(sizeof(MazeStep));
    	pHead->next=pHead;
    	pHead->prior=pHead;
    	return pHead;
    }
    
    //向链表尾插入新的节点(迷宫中为尾结点,此处也是插尾),在操作第一个节点时，别忘了初始化 
    void InsertMazeStep(MazeStep *pHead,int x,int y,int direction){
    	
    	MazeStep *pNew=(MazeStep *)malloc(sizeof(MazeStep));
    	pNew->x=x;
    	pNew->y=y;
    	pNew->direction=direction;
    	
    	pHead->prior->next=pNew;
    	pNew->prior=pHead->prior;
    	 
    	pNew->next=pHead;
    	pHead->prior=pNew;	
    } 
    
    
    //判断链表是否为空,为空是1,否则为0 
    int StepEmpty(MazeStep *pHead){
    	if(pHead->next==pHead)  return 1;
    	else return 0;
    }
     
    //删除链表中的某个节点(迷宫中为尾结点,此处也是删尾),删除前别忘了判断链表是否为空 
    void DeleteStep(MazeStep *pHead){
    	MazeStep *pTemp;
    	pTemp=pHead->prior;
    	
    	pTemp->prior->next=pHead;
    	pHead->prior=pTemp->prior; 
    	free(pTemp);
    } 
    
    //输出函数,测试用 
    void PrintfStep(MazeStep *pHead){
    	MazeStep *pTemp=pHead->next;
    	while(pTemp!=pHead){
    		printf("x=%d,y=%d,direction=%d\n",pTemp->x,pTemp->y,pTemp->direction);
    		pTemp=pTemp->next;
    	}	
    } 
    
    //初始化迷宫 
    int **InitMaze(){
    	int temp;
    	printf("请输入迷宫的行数：");
    	scanf("%d",&m_row);
    	printf("请输入迷宫的列数："); 
    	scanf("%d",&m_col);
    	int **maze=CreatElem();//记录初始迷宫 
    	
    	printf("请设置迷宫障碍物(1)与非障碍物(0)\n");
    	
    	for(int i=1;i<=m_row;i++)
    	for(int j=1;j<=m_col;j++){
    		scanf("%d",&temp);
    		maze[i][j]=temp;
    	} 	
    	
    	//printf("*********************************\n");
    	//PrintMaze(maze);
    	return maze; 	
    }
    
    //用来标记每个元素是否走过 
    int **InitBook(){
    	int **book=CreatElem();
    	for(int i=1;i<=m_row;i++)
    	for(int j=1;j<=m_col;j++)
    		book[i][j]=0;
    		
    	return book; 
    } 
    
    //用来生成一个row行col列的动态二维数组,存迷宫,和标记 
    int **CreatElem(){
    	int **array=(int **)malloc((m_row+1)*sizeof(int *));//先申请Row个第一维指针用来存放一位数组的首指针 
    	for(int i=1;i<=m_row;i++) 
    	array[i]=(int *)malloc((m_col+1)*sizeof(int));//申请第二维数组,用完别忘了free()哟！ 
    	return array;
    }
    
    //打印二维指针数组内容 
    void PrintMaze(int **array){
    	for(int i=1;i<=m_row;i++){
    	for(int j=1;j<=m_col;j++)
    		printf("%d ",array[i][j]);
    		printf("\n");
    	} 	
    }
    
    //用完数组后free()操作 
    void FreeMaze(int **array){
    	for(int i=1;i<m_row+1;i++) 
    	free(array[i]);//申请时先申请一维,再二维;free()时,相反 
    	free(array);
    	printf("free完成\n");
    } 
    
    
    //用次函数前一定要判断,边界 
    void DirectionStep(int *x,int *y,int direction){
    	
    	switch(direction){
    		case 1:*x=*x+1;break;
    		case 2:*y=*y+1;break;
    		case 3:*x=*x-1;break;
    		case 4:*y=*y-1;break;
    	}	
    } 
    
    //判断下一个方向的坐标是否越界,是返回1,否则返回0 
    int Barrier(int row,int col,int x,int y,int **book,int **maze){
    	if(x<=col&&x>=1&&y<=row&&y>=1&&book[y][x]==0&&maze[y][x]==0) 
    	return 0;     
    	return 1;
    }
    
    
    //打印成功路线图 
    void PrintOKStep(MazeStep *pHead){
    	printf("\n\n第%d种方法\n\n",count++);
    		
    	int **print=InitBook();
    				
    	for(int i=1;i<=m_row;i++)
    	for(int j=1;j<=m_col;j++)
    	print[i][j]=1;	
    				
    	MazeStep *pTemp=pHead->next;
    	while(pTemp!=pHead){
    	print[pTemp->y][pTemp->x]=0;
    	pTemp=pTemp->next;
    	}	
    				
    	print[m_row][m_col]=0; 
    	PrintMaze(print);			
    }	
    
    //迷宫的入口默认为(1,1),出口默认为(m_row,m_col) 
    void MazeMap(){
    	
    	int flag=0;
    	int x,y;
    	int px=1,py=1;
    	
    	int **maze=InitMaze();
    	int **book=InitBook();
    	MazeStep *pHead=CreatMazeStep();
    
    	for(int direction=1;direction<=4;direction++){
    		flag=0;
    		x=px;
    		y=py;
    		
    		DirectionStep(&px,&py,direction);
    		
    		if(Barrier(m_row,m_col,px,py,book,maze)==0){
    			if(px==m_col&&py==m_row)  PrintOKStep(pHead); 
    			else{
    				flag=1;
    				book[y][x]=1;
    				InsertMazeStep(pHead,x,y,direction);	
    				direction=0;
    				}
    			}
    		
    		if(flag==0){ px=x; py=y;}
    		
    		if(direction==4){
    			while(StepEmpty(pHead)==0){
    			px=pHead->prior->x;
    			py=pHead->prior->y;
    			direction=pHead->prior->direction;
    	
    			if(direction==4) { book[py][px]=0; DeleteStep(pHead);}
    			else { book[py][px]=0; DeleteStep(pHead);break;}
    			}
    		}	
    	}//for后面括号 
    
    }
    
    
    	 
    int main(){
    	MazeMap();
    	return 0;
    } 	
    	
    
    
    
    
    
    
    
    
    
    /*
    测试数据
    0 0 1 0 0 0 1 0
    0 0 1 0 0 0 1 0
    0 0 0 0 1 1 0 1
    0 1 1 1 0 0 1 0
    0 0 0 1 0 0 0 0
    0 1 0 0 0 1 0 1
    0 1 1 1 1 0 0 1
    1 1 0 0 0 1 0 1
    1 1 0 0 0 0 0 0
    
    
    */