数据结构课程设计：迷宫问题（一）

太过爱你忘了你带给我的痛 2023-07-23 15:56 22阅读 0赞

## 一、实验要求： ##

*  **问题描述**  
    以一个m\*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
 *  **基本要求**
    
     *  实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
     *  编写递归形式的算法，求得迷宫中所有可能的通路；
     *  以方阵形式输出迷宫及其通路

## 二、结构框架： ##

![图1][1]

## 三、代码 ##

### 主函数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTQyMQ_size_16_color_FFFFFF_t_70]

int main()
    {
        
    	//初始化迷宫 
    	cout<<("这是一个m行n列，以左上角为起点，右下角为终点的迷宫")<<endl;
    	cout<<("\n请输入迷宫的行和列数：")<<endl;
    	cin>>m>>n;
    	int **maze=new int *[m+2];
        for(int i=0;i<m+2;i++){
        
            maze[i]=new int[n+2];
        }
         //在迷宫四周增加障碍墙 
        for(int i=0;i<m+2;i++){
        
            maze[i][0]=maze[i][n+1]=1;
        }
        for(int i=0;i<n+2;i++){
        
            maze[0][i]=maze[m+1][i]=1;
        }
    	cout<<("请选择迷宫生成方式：0随机产生，1手动输入")<<endl;
    	cin>>choice;
    	if(choice){
        
    		while(flag) initMaze(maze);
    	} 
    	else createMaze(maze); 
    	//利用栈求通路并以三元组形式输出 
    	cout<<("\n用栈实现深度优先搜索求得通路：")<<endl; 
    	dfsFindPath(maze);
    	cout<<("\n用栈实现宽度优先搜索求最短路：")<<endl;
    	bfsFindPath(maze);
    	//递归求得所有通路并自选形式输出 
    	if(flag){
        
    		cout<<("\n递归求得迷宫中所有可能的通路：")<<endl;
    		allPaths(maze,1,1);
    	}
    	cout<<"以上是全部路径"; 
    	//system("pause");
    	return 0;
    }

#### PartⅠ.以链表作为存储结构的栈操作 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTQyMQ_size_16_color_FFFFFF_t_70 1]

struct position
    {
        
    	int row,col;
    	int direction;
    };
    struct node
    {
        
    	position data;
    	node *next;
    };
    class stack
    {
        
    	private:
    		int StackSize;
    		node *StackTop;
    	public:
    		stack():StackSize(0),StackTop(NULL){
        };
    		~stack();
    		bool empty() const{
         return StackSize==0; }
    		int size() const{
         return StackSize; }
    		position top(){
        
    			if(StackSize==0){
        
    				cout<<"empty stack"<<endl;
    			}
    			else return StackTop->data;
    		}
    		node* topNode(){
        //便于栈的输出
    			if(StackSize==0) cout<<"empty stack"<<endl;
    			else return StackTop;
    		}
    		void pop();
    		void push(position onePosition){
        
    			node *p=new node;
    			p->data=onePosition;
    			p->next=StackTop;
    			StackTop=p;
    			StackSize++;
    		}
    	friend  ostream& operator<<(ostream& output,stack &s); 
    };
    stack::~stack()
    {
        
        node *p;
        while(StackTop){
        
            p=StackTop->next;
            delete StackTop;
            StackTop=p;
        }
        StackSize=0;
    }
    void stack::pop()
    {
        
    	if(empty()){
        
    		cout<<("empty stack")<<endl;
    		return;
    	}
    	node *p=StackTop;
    	StackTop=StackTop->next;
    	delete p;
    	StackSize--;	
    }
    ostream& operator<<(ostream& output,stack &s)//重载运算符实现三元组形式输出
    {
        
           if(s.empty()){
        
                output<<"empty stack"<<endl;
           }
           else{
        
                node *p=s.topNode();
                while(p){
        
                 	output<<"("<<p->data.row<<","<<p->data.col<<",";
                    switch(p->data.direction){
        
               	       case 0:
                    		output<<"→"<<")\n";break;
                	   case 1:
                    		output<<"↓"<<")\n";break;
                	    case 2:
                   	 	 	output<<"←"<<")\n";break;
                	    case 3:
                   			output<<"↑"<<")\n";break;
                        case 4:
                    		output<<"★"<<")\n";break;
                	   }
                    p=p->next;
                }
    
           }
           return output;
    }

`int dRow[4]={0,1,0,-1},dCol[4]={1,0,-1,0};//右、下、左、上`

##### Part Ⅱ.初始化迷宫 #####

1.手动输入：

void initMaze(int** maze)//创建迷宫
    {
        
    //    int **maze=new int *[m+2];
    //    for(int i=0;i<m+2;i++){
        
    //        maze[i]=new int[n+2];
    //    }
        cout<<"请输入迷宫分布:（用0和1分别表示通路和障碍，以空格分隔）"<<endl;
        for(int i=1;i<=m;i++){
        
            for(int j=1;j<=n;j++){
        
    		cin>>maze[i][j];
            }
        }
        if(maze[1][1]==1){
        
    	cout<<("抱歉，入口处不可设置障碍物，请重新输入迷宫分布")<<endl;
    	return;
        }
        flag=false;
    //    //在迷宫四周增加障碍墙 
    //    for(int i=0;i<m+2;i++){
        
    //        maze[i][0]=maze[i][n+1]=1;
    //    }
    //    for(int i=0;i<n+2;i++){
        
    //        maze[0][i]=maze[m+1][i]=1;
    //    }
    }

2.随机生成（Prim算法）

*  算法原理：  
    （1）初始地图所有位置均设为障碍墙；  
    （2）任意插入一个墙体进墙队列；  
    （3）判断此时墙体是否可以设置为路（判断依据：上下左右四个位置是否只有一个位置是路）；  
    （4）若设置为路，则将该位置四周所有的墙插入队列，接着执行（5）；若无法设置为路，直接执行（5）；  
    （5）从墙队列中删去当前位置所在节点；  
    （6）若墙队列不为空，则从队列中随机选取一处障碍重新执行（3），直到墙队列为空。

void createMaze(int** MAZE){
        
    	int maze[m+4][n+4];
        for(int i=0;i<m+4;i++){
        
        	for(int j=0;j<n+4;j++){
        
        		maze[i][j]=1;
    		}	
    	}
        //将迷宫四周设为通路，保护障碍墙，防止出界
        for(int i=0;i<m+4;i++){
        
            maze[i][0]=maze[i][n+3]=0;
        }
        for(int i=0;i<n+4;i++){
        
            maze[0][i]=maze[m+3][i]=0;
        }
        vector<int> X,Y;
        X.push_back(2);
        Y.push_back(2);
        while (X.size()) {
        
    		//在墙队列中随机取一点
    		srand((unsigned int)(time(NULL)));
    		int index=rand()%(X.size());
    		int x=X[index];
    		int y=Y[index];
    		//判读上下左右四个方向是否为路
    		int count = 0;
    		int r,c;
    		for(int i=0;i<4;i++){
        
    			r=x+dRow[i];c=y+dCol[i];
    			if(maze[r][c]==0)
    				count++;
    		} 
    		if(count<=1){
        
    			maze[x][y]=0;
    			for(int i=0;i<4;i++){
        
    				r=x+dRow[i];c=y+dCol[i];
    				if(maze[r][c]==1){
        
    					X.push_back(r);
    					Y.push_back(c);
    				}
    			}
    
    		}
    		//删除当前墙
    		X.erase(X.begin()+index);
    		Y.erase(Y.begin()+index);
    	}
    	for (int i = n- 3; i >= 0; i--) {
        
    		if (maze[i][n - 3] == 0) {
        
    			maze[i][n - 2] = 0;
    			break;
    		}
    	}
    	maze[m+1][n+1]=0;
    	cout<<"随机生成的迷宫为："<<endl; 
    	for(int i=1;i<=m;i++){
        
    		for(int j=1;j<=n;j++){
        
    			MAZE[i][j]=maze[i+1][j+1];
    			cout<<MAZE[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    }

##### Part Ⅲ.利用栈求通路，以三元组形式输出： #####

**①dfs求通路:**

void dfsFindPath(int **maze)
    {
        
    	stack path;
    	position here={
        1,1,0};
    	maze[1][1]=2;
    	int option=0;
    	while(here.row!=m||here.col!=n){
        
    		//没有到达出口，找要移动的相邻一步
    		int r,c;
    		while(option<4){
        //0、1、2、3四个方位 
    			r=here.row+dRow[option];
    			c=here.col+dCol[option];
    			if(maze[r][c]==0)break;
    			option++;
    		}
    		if(option<4){
        //找到相邻一步 
    			here.direction=option;
    			path.push(here);
    			here.row=r;
    			here.col=c;
    			maze[r][c]=2;
    			option=0;
    		}
    		else{
        //邻近没有通路，回溯 
    			if(path.empty()){
        
    				cout<<("No path.")<<endl;
    				return;
    			}
    			position prev=path.top();
    			path.pop();
    			if(prev.row==here.row)
    				option=2+prev.col-here.col;
    			else option=3+prev.row-here.row;
    			here=prev;//回到前一个点走下一步 
    		}
    	}
    	//到达出口将出口入栈以便路径完整输出
    	path.push((position){
        m,n,4}); 
    	//利用新栈实现正序输出，并还原maze 
    	stack orderedPath;
    	while(!path.empty()){
        
    		orderedPath.push(path.top());
    		path.pop();
    	}
    	cout<<orderedPath;
    	remaze(maze); 
    }

**②bfs求最短路**

void bfsFindPath(int **maze)
    {
        
    	position prePos[m+1][n+1];//记录上一个position
    	stack in,out;
    	position here,next;
    	maze[1][1]=2;
    	out.push({
        1,1,0});//起点入队 
    	while(!in.empty()||!out.empty()){
        
    		//出队
    		if(out.empty()){
        
    			while(!in.empty()){
        
    				out.push(in.top());
    				in.pop();
    			}
    		}
    		here=out.top();
    		out.pop();
    		if(here.row==m&&here.col==n){
        //到达出口
    			flag=true;
    			break;
    		}
    		for(int i=0;i<4;i++){
        
    			int r=here.row+dRow[i];
    			int c=here.col+dCol[i];
    			if(maze[r][c]==0){
        
    				maze[r][c]=2;
    				here.direction=i;//记录方向 
    				prePos[r][c]=here;
    				next.row=r;
    				next.col=c;
    				in.push(nex);//下一个入队 
    			}
    		}
    	}
    	if(flag){
        
    		//从终点向起点回溯，此时here.row=m here.col=n 
    		stack path;
    		path.push({
        m,n,4});
    		while(here.row!=1||here.col!=1){
        
    			here=prePos[here.row][here.col];
    			path.push(here);
    		}
            //利用栈FIFO思想直接正序输出
    		cout<<path;
    	}
    	else cout<<("No path.");
    	remaze(maze);	
    }

##### Part Ⅳ.（DFS）递归求所有通路，以三元组或方阵形式输出： #####

stack path;
    int rank=1;
    bool choice;
    void printPath();
    void printPath(int** maze);
    void allPaths(int **maze,int row,int col)
    {
        
    	if(row==m&&col==n){
        
    		maze[m][n]=6;
    		path.push({
        m,n,4});
    		cout<<"第"<<(rank++)<<"条路径："<<endl;
    		cout<<("请选择输出方式：输入0为三元组形式，1为方阵形式")<<endl;
    		cin>>choice;
    		if(choice) printPath(maze);
    		else printPath();
    		maze[m][n]=0;
    		path.pop();
    		return;
    	}
    	for(int i=0;i<4;i++){
        
    		int r=row+dRow[i];
    		int c=col+dCol[i];
    		if(maze[r][c]==0){
        
    			maze[row][col]=i+2;
    			path.push({
        row,col,i});
    			allPaths(maze,r,c);
    			maze[row][col]=0;
    			path.pop();	
    		}
    	}
    }

重载printPath函数，分别实现栈的三元组形式输出和迷宫的方阵形式输出。

void printPath(){
        
    	stack orderedPath;
    	node* p=path.topNode();
    	while(p){
        
    		orderedPath.push(p->data);
    		p=p->next;
    	}
    	cout<<orderedPath;
    }
    void printPath(int **maze)
    {
        
    	cout<<("注：.代表通路，#代表障碍物，*代表终点")<<endl;
    	for(int i=1;i<=m;i++){
        
    		for(int j=1;j<=n;j++){
        
    			if(maze[i][j]==0)
    				cout<<". ";	
    			else if(maze[i][j]==1)
    				cout<<"# ";
    			else{
        
    				switch(maze[i][j]-2)
    				{
        
    	        		case 0:
    	               		cout<<"> ";break;
    	            	case 1:
    	                	cout<<"V ";break;
    	            	case 2:
    	               	 	cout<<"< ";break;
    	            	case 3:
    	               		cout<<"A ";break;
    	               	case 4:
    	                	cout<<"* ";break;
    	            }
    			}
    		}
    		cout<<endl;
    	}
    }

[1]: /images/20230528/eefc587e8d564fbc8402780c3fe799c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTQyMQ_size_16_color_FFFFFF_t_70]: /images/20230528/1efd0225041f4dcab690326a5a414fae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTQyMQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/1de73cd4f972428e80dd0467a75d6672.png