精华内容
下载资源
问答
  • 数据结构与算法——迷宫问题
    2021-12-21 11:32:44

    课程名称:数据结构与算法

    设计题目:迷宫问题

    已知技术参数和设计要求:

    问题描述:

    以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口(1,1)到出口(m,n)的一条通路,或得出没有通路的结论。

    基本要求:

    首先实现一个以链表作存储结构的栈类型,然后编写一个求迷宫问题的非递归程序,求得的通路以三元组(ijd)的形式输出,其中:(ij)指示迷宫中的一个坐标, d表示走到下一坐标的方向。

    测试数据:

    迷宫用伪随机数产生程序产生。

    左上角(1,1)为入口,右下(m,n)为出口。

    选作内容:

    1.编写递归形式的算法,求得迷宫中的所有可能的通路。

    2.以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路。

    基本思路:

    1.创建一个二维数组代表迷宫,另外在创建一个的等大且初值全为“0”的二维数组,用来在寻找通路的函数中记录位置。

    2.创建一个栈结构体,用来存储路线(走过的点压进栈,走不通返回则弹栈)。

    3.定义上、下、左、右、上左、上右、下左、下右八个遍历方向(如果是四个方向的话非常容易出现死路,且不符合实际)。

    代码及相关注释如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include<time.h>
    
    #define size 100
    #define M 100
    #define N 100
    
    typedef struct
    {
    	int x;//横
    	int y;//纵
    }position;
    
    typedef struct stack
    {
    int row;//行
    int col;//列
    int dir;//方向
    }date;
    
    typedef struct//定义栈 
    {
    	date stack[size] ;
    	int top;
    }tstack;
    
    position direction[8]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};//八个遍历方向 
    
    int sum=0;
    int maze[M][N];
    int maze_2[M+2][N+2]={0};//等大全为0的数组 
    int m,n;
    
    void push(tstack*s,date x)//压栈 
    {
    	if(s->top==size-1)//从0开始,所以size-1 
    	printf("栈满了");
    	else
    	{
    		s->top++;
    		s->stack[s->top]=x;//把x赋给top指向的栈顶 
    	}
    }
    
    void pop(tstack*s)//弹栈 
    {
    	if(s->top==-1)//判断栈顶的值来判断是否为空栈 
    	printf("栈空");
    	else
    	{
    		s->top--;//弹出栈顶元素 
    	}
    }
    
    void print_path(int sum,tstack s)
    {
    	int a;
    	printf("第 %d 条通路:\n",sum);
    	for(a=0;a<s.top;a++)
    	printf("(%d,%d,%d)->",s.stack[a].row ,s.stack[a].col,s.stack[a+1].dir );//输出栈里的元素 ,三元坐标 
    	printf("出口\n"); 
    	printf("\n");	 
    }
    
    void path(int x,int y,tstack e)//寻找迷宫的通路 
    {	
    int i,a,b,c;
    date t;//引用结构体date 
    if(x==m&&y==n)//判断是否到(m,n)出口 
    {
    	sum++;
    	print_path(sum,e);//调用打印迷宫(print_path)函数 
    	}	
    	else
    	{
    		for(i=0;i<8;i++)//遍历八个方向 
    		{
    			a=x+direction[i].x;//判断走向 
    			b=y+direction[i].y;
    			c=i;
    			if(!maze[a][b]&&!maze_2[a][b])//可以走的路,相当于if(1&&1) 
    			{
    				t.row=a;
    				t.col=b;
    				t.dir=c;
    				maze_2[a][b]=maze[a][b]=1;//走过的地方在maze和maze_2中标记为1 
    				push(&e,t);//然后存到栈里面去 
    				path(a,b,e);//在path函数自身调用path函数 ,获得点 
    				maze_2[a][b]=maze[a][b]=0;//将位置清空,表示没有走过的路 
    				pop(&e);//走不通的点,弹栈弹出走不通的点 
    			}
    		}
    	}
    }
    
    /*主函数部分*/ 
    int main()
    {
    int a,b;
    
    tstack *s;//初始化栈 
    s=(tstack *)malloc(sizeof(tstack));
    s->stack[0].row =1;
    s->stack[0].col=1;
    s->top=0;
    
    maze_2[1][1]=maze[1][1]=1;
    
    printf("输入迷宫行数和列数:\n");
    scanf("%d %d",&m,&n);
    
    srand((unsigned)time(NULL));//随机迷宫 
    for(a=0;a<m+2;a++)
    {
    	for(b=0;b<n+2;b++)
    	{
    		maze[a][b]=rand()%2;//只有0和1的随机迷宫
    		if(a==m&&b==n) 
    		{
    		maze[a][b]=0;//出口设为0 
    		maze[1][1]=0; //入口设为0 
    	}
    	}
    }
    for (a = 0; a < n + 2; a++) maze[0][a] = 1;//上 墙 (上下左右的墙用1代表,即为输出中的“#”) 
    for (a = 0; a < m + 2; a++) maze[a][0] = 1;//左 墙 
    for (a = 0; a < n + 2; a++) maze[m+ 1][a] = 1;//下 墙 
    for (a = 0; a < m + 2; a++) maze[a][n + 1] = 1;//右 墙 
    for (a = 0; a < n; a++) maze[m][a] = 1;
    
    printf("随机迷宫:\n");
     for(a=0;a<m+2;a++)
    {
    	for(b=0;b<n+2;b++)
    	{
    	if (maze[a][b] == 1)
    	printf("#");//“#”代表墙 
    	else if(maze[a][b]==0)
    	printf(" ");//“ ”代表可到到达的地方 
    }
    printf("\n");
    }
     path(1,1,*s);//调用path函数得到通路 
    return 0;
    }
    

       注意:本代码仅供参考!

    更多相关内容
  • 通过手动输入迷宫,1代表墙,0代表通路,编写算法实现手动输入,找到合适路径,输出。
  • 数据结构 迷宫算法

    2018-12-20 12:49:57
    用栈来求解迷宫数据结构实验。求解迷宫的代码来自书上,迷宫只能在源代码上修改。
  • 数据结构与算法 迷宫问题

    千次阅读 2019-03-08 22:09:59
    迷宫问题问题描述: 栈的实现在这篇博客中:https://blog.csdn.net/zj1131190425/article/details/87991662 迷宫是一个矩形区域,有一个出口和入口,迷宫内部包含不能穿越的墙壁和障碍物。 1.用矩阵来描述迷宫。...

    迷宫问题问题描述:

    栈的实现在这篇博客中:https://blog.csdn.net/zj1131190425/article/details/87991662

    迷宫是一个矩形区域,有一个出口和入口,迷宫内部包含不能穿越的墙壁和障碍物。

    1.用矩阵来描述迷宫。入口是(0, 0), 出口是(m,n),现在需要在迷宫中选找一条路径,穿过迷宫。位置(i,j)=1表示有障碍。0表示无障碍。

    思路:

    1.出发点处,定义四个方向的坐标偏移量,搜索等四个方向,直到找到一个可行的方向,按照可行的方向移动到下一个位置,将前一个位置坐标压入栈中(保存路径),且将此位置设置为1(放置障碍物,防止往回退的时候又重新搜索这个方向)

    2. 如果在某个位置没有找到可行的方向,则将当前这个位置设置为1(这个位置不可再回来),从栈顶弹出一个坐标,作为当前坐标(相当于走回头路),继续搜索其他的方向是否可行。

    3. 如此往复

    采用自顶向下设计的方法设计代码:

    (1)输入迷宫

    (2)寻找路径

    (3)输出路径

    #include <iostream>
    #include "E:\back_up\code\c_plus_code\sparseMatrix\external_file\arraystack.h"
    #include <string>
    using namespace std;
    
    // 迷宫
    template<typename T>
    void print_array(T a[][12])
    {
    	for(int i=0; i<12; i++)
    	{
    		for(int j=0; j<12; j++)
    		{
    			cout << a[i][j] << " ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    }
    
    
    class position    // 存储位置坐标 
    {
    	public:
    	int row;
    	int col;
    	position()
    	{
    		row = 0;
    		col = 0;
    	}
    	
    	position(int row, int col)
    	{
    		this->row = row;
    		this->col = col;
    	}
    	
    	void add_offset(position& ps)
    	{
    		row += ps.row;
    		col += ps.col;
    	} 
    }; 
    
    
    
    void find_path(bool map[][12])
    {
    	int map_1[12][12];
    	// 保存map()的一个副本
    	for(int i=0; i<12; i++)
    	{
    		for(int j=0; j<12; j++)
    		{
    			map_1[i][j] = (int)map[i][j];
    		}
    	} 
    	// 寻找迷宫的路径
    	arrayStack<position> path; // 存储路径信息
    
    	// 偏移量
    	position offset[4];
    	
    	// 向右偏移  index=0 
    	offset[0].row = 0;
    	offset[0].col = 1; 
    	// 向下偏移  index=1
    	offset[1].row = 1;
    	offset[1].col = 0;
    	// 向左偏移   index=2
    	offset[2].row = 0;
    	offset[2].col = -1;
    	// 向上偏移   index=3
    	offset[3].row = -1;
    	offset[3].col = 0; 	
    	
    	position current_position(1,1);   // 初始化当前位置
    	int option = 0;  //初始化选的方向,右,下,左,上=(0,1,2,3)
    	int max_otion = 3;   // 方向的选择范围
    	
    	map[1][1] = 1;   // 在(1,1)位置放置障碍 
    	cout << "current position: " << current_position.row << "  " << current_position.col << endl;
    
    	while(current_position.row!=10 || current_position.col!=10)
    	{
    		
    		int r,c;
    		while(option<=max_otion)
    		{
    			r = current_position.row + offset[option].row;
    			c = current_position.col + offset[option].col;
    			if(map[r][c]==0)   // 新的位置可行
    			{
    				break;
    			} 
    		    option++;
    		}
    		
    		if(option<=max_otion)  // 找到了可行的方向
    		{
    			path.push(current_position); 
    			//current_position.add_offset(offset[position]);    // current_position更新 
    			
    			current_position.row = r;    // 移动到新的位置 
    			current_position.col = c;
    			
    			map[r][c] = 1;  // 放置障碍物  避免回退时又选到这个方向 
    			option = 0; 
    		} 
    		
    		else     // 选择的位置走不通 
    		{
    			if(path.empty())
    	        {
            		cout << "The puzzle has no solution" << endl;
            		return;
            	}
            	
            	position next = path.top();
            	path.pop();
            	// 计算返回后的搜索方向:
    			// 按照前面对方向的定义,返回后应该搜索未搜索过的两个方向:
    			// map[currentRow][currentCol] = 1;  // 走不通的位置设置障碍,避免重复搜索 
    			map[current_position.row][current_position.col] = 1;   // 当前的位置是死路 
    			option = 0;
    			current_position = next;   // 浅复制即可 这个类默认的拷贝构造函数 
    		}
    		cout << "(r,c)= " << r << "," << c << endl;
    	}
    	
    	position tmp;
    	while(!path.empty())
    	{
    		// cout << "revise the map" << endl;
    	    tmp = path.top();
    	    path.pop();
    	    map_1[tmp.row][tmp.col] = 2;
    	}
    	
    	// 结果输出 
    	char result[12][12];
    	for(int i=0; i<12; i++)
    	{
    		for(int j=0; j<12; j++)
    		{
    			if(map_1[i][j]==1)
    			{
    				result[i][j]='1';
    			}
    			else if(map_1[i][j]==0)
    			{
    				result[i][j]='0';
    			}
    			else
    			{
    				result[i][j]='*';
    			}
    		}
    	}
    
    	print_array(result); 	
        
    	
    }
    
    
    int main(int argc, char *argv[])
    {
        //int a[12][12];
        bool a[][12] = {
    				     {1,1,1,1,1,1,1,1,1,1,1,1},
    				     {1,0,1,1,1,1,1,0,0,0,0,1},
    				     {1,0,0,0,0,0,1,0,1,0,0,1},
    				     {1,0,0,0,1,0,1,0,0,0,0,1},
    					 {1,0,1,0,1,0,1,0,1,1,0,1},
    					 {1,0,1,0,1,0,1,0,1,0,0,1},
    					 {1,0,1,1,1,0,1,0,1,0,1,1},
    					 {1,0,1,0,0,0,1,0,1,0,1,1},
    					 {1,0,1,0,1,1,1,0,1,0,0,1},
    					 {1,1,0,0,0,0,0,0,1,0,0,1},
    					 {1,0,0,0,0,1,1,1,1,0,0,1},
    			 		 {1,1,1,1,1,1,1,1,1,1,1,1} 
    			        };
        //print_array(a);
        find_path(a);
        return 0;
    }
    
    

    运行结果:

    迷宫问题最短路径

    可以使用队列来实现寻找最短路径的操作

    首先介绍C++ 实现队列:关于队列的实现参考博客: https://blog.csdn.net/zj1131190425/article/details/88090905,下面的队列是对https://blog.csdn.net/zj1131190425/article/details/88090905中队列的改进,主要是改经了ensureCapacity()函数,因为原来的队列中ensureCapacity()函数有点小的bug.

    定义一个队列的基类,queueABC

    queueABC.h文件

    #ifndef QUEUE_ABC_H
    #define QUEUE_ABC_H
    
    using namespace std;
    // 定义抽象类
    template<typename T>
    class queueABC
    {
    	public:
    	// virtual ~queue();
    	virtual bool empty() const=0;  // 纯虚函数 只读
    	virtual int size() const=0;    // 返回队列中元素的个数   
    	virtual T& front() = 0;        // 返回队首元素
    	virtual T& back() = 0;         // 返回队尾元素
    	virtual void pop() = 0;        // 删除队首的元素
    	virtual void push(T x) = 0;    // 队尾插入元素 
    };
    #endif
    

    queue.h

    #ifndef QUEUE_H
    #define QUEUE_H
    
    #include <iostream>
    #include <algorithm>
    #include "E:\back_up\code\c_plus_code\dequeue\external_file\queueABC.h"   // 包含ABC文件 
    #include "E:\back_up\code\c_plus_code\dequeue\external_file\queueemptyEx.h"   // 包含异常类文件 
    using namespace std;
    
    template<typename T>
    class queue : public queueABC<T>
    {
    	private:
    	int arrayLength;  // 数组的长度
    	int queueSize;   // 队列中元素的个数
    	int queueFront;   // 队首元素所在的位置
    	int queueBack;    // 队尾元素所在的位置
    	T* element; 
    	void ensureArrayLength();   // 进行数组扩容 
    	
    	public:
    	queue(int arrayLength=10);    // 构造函数 
    	~queue();                     // 析构函数 
    	queue(const queue& q);        // 拷贝构造函数 
    	
    	// ADT 
    	bool empty() const;
    	int size() const;
    	T& front();
    	T& back();
    	void pop();
    	void push(T x);
    	void display_queue() const;   // 打印输出队列中的元素 
    	
    };
    
    template<typename T>
    queue<T>::queue(int arrayLength)
    {
    		this->arrayLength = arrayLength;
    		this->queueSize = 0;
    		this->queueFront = 0;
    		this->queueBack = 0;
    		element = new T[arrayLength];
    }
    
    template<typename T>
    queue<T>::~queue()
    {
    	delete [] element;
    } 
    
    template<typename T>
    queue<T>::queue(const queue& q)
    {
    	arrayLength = q.arrayLength;
    	queueSize = q.queueSize;
    	queueFront = q.queueFront;
    	queueBack = q.queueBack;
    	element = new T[arrayLength];
    	for(int i=0; i<queueSize; i++)
    	{
    		element[i] = q.element[i];
    	}
    } 
    
    template<typename T>
    bool queue<T>::empty() const
    {
    	return queueSize==0;
    } 
    
    template<typename T>
    int queue<T>::size() const
    {
    	return queueSize;
    }
    
    template<typename T>
    T& queue<T>::front()
    {
    	return element[(queueFront+1)%arrayLength];  // queueFront是队首元素的前一个位置,+1是表示队首元素的位置 
    }
    
    template<typename T>
    T& queue<T>::back()
    {
    	return element[queueBack%arrayLength];    // queueback队尾元素的位置 
    }
    
    /*
    template<typename T>
    void queue<T>::ensureArrayLength()
    {
    	// 如果需要,增加数组长度 
    	if((queueBack+1)%arrayLength==queueFront)   // 环形的数组 
    	{
    		T* old;
    		old = element;
    		//delete element;
    		// arrayLength = arrayLength*2;   // 增加分配的内存长度 
    		element = new T[2*arrayLength]; 
    		// 环形数组重新布局
    		// 先将数组复制过来
    		//更新关于数组复制
    		int index_tmp;
    	    for(int i=0; i<queueSize; i++)
    	    {
        		index_tmp = (queueFront+1+i)%arrayLength;
        		element[index_tmp] = old[index_tmp];
        	}
    		 
    		delete old;
    		// 重新布局  // 分为三种情况:1.queuefront=0; queuefront==arrayLength-1; else;
    		int pre_start = queueFront%arrayLength;  // 队列首元素的前一个位置 
    		if(pre_start==0)
    		{
    			// 移动所有的数组元素 
    			for(int i=0; i<queueSize; i++)
    			{
    				element[2*arrayLength-1-i] = element[(queueBack%arrayLength)-i];
    			} 
    			queueFront = queueFront + arrayLength;
    			queueBack = queueBack + arrayLength;
    		} 
    		else if(pre_start==arrayLength-1)   // arrayLength还是原来的值 
    		{
    			// 不用移动数组元素,之更改front 
    			queueFront = queueFront + arrayLength; 
    		}
    		else
    		{
    			// 移动第二段的元素:
    			int element_to_move = arrayLength-1-(queueFront%arrayLength);  // 计算第二段需要移动的元素的数量 
    			for(int i=0; i<element_to_move; i++)
    			{
    				element[2*arrayLength-1-i] = element[queueBack%arrayLength-i];
    			} 
    			queueFront = queueFront + arrayLength;
    		}
    		arrayLength = arrayLength*2;   // 更新arrayLength 		 
    	}
    	// 添加一个动态减少内存的函数 
    }
    */
    
    template<typename T>
    void queue<T>::ensureArrayLength()
    {
    	if((queueBack+1)%arrayLength==queueFront)   // 环形的数组 
    	{
    		T* new_element = new T[2*arrayLength];
    		int start = (queueFront+1)%arrayLength;
    		if(start<2)   // 没有形成环
    		{
    			copy(element+start, element+start+arrayLength-1, new_element);    // 复制操作 
    		} 
    		else   // 形成环
    		{
    			copy(element+start, element+arrayLength, new_element);
    			copy(element, element+queueBack+1, new_element+arrayLength-start);
    		} 
    		queueFront = 2*arrayLength-1;
    		queueBack = arrayLength-2;
    		arrayLength *= 2;
    		delete[] element;
    		element = new_element;
    	}
    }
    
    // push()操作:
    template<typename T>
    void queue<T>::push(T x)
    {
    	ensureArrayLength();     // 先保证数组长度满足条件
    	queueSize++;
    	//queueBack = (queueBack+1)%arrayLength;
    	//element[queueBack] = x;	 
    	queueBack++;
    	element[queueBack%arrayLength] = x;
    } 
    
    //pop()操作 
    template<typename T>
    void queue<T>::pop()
    {
    	if(empty())
            throw queueEmptyException(0); 
    	queueFront++;
    	queueSize--;
    	// element[queueFront].~T;
    } 
    
    template<typename T>
    void queue<T>::display_queue() const
    {
    	//int tmp = queueFront;
    	// int start_pos = (tmp+1)%arrayLength;
    	if(empty())
    	{
    		cout << "The queue is empty!" << endl;
    		return;
    	}
    	
    	for(int i=0; i<queueSize; i++)
    	{
    		cout << element[(queueFront+1+i)%arrayLength] << " ";
    	}
    	cout << endl;
    }
    
    #endif 

    自定义的异常类:

    queueemptyException:

    // 自定义异常类
    #ifndef QUEUE_EMPTY_EXCEPTION
    #define QUEUE_EMPTY_EXCEPTION
    #include <stdexcept>
    #include <iostream>
    using namespace std;
    
    class queueEmptyException : public runtime_error
    {
    	private:
    	int queueSize;
    	
    	public:
    	queueEmptyException(int queueSize) : runtime_error("The queue empty!")
    	{
    		this->queueSize = queueSize;
    	}
    	
    	void display_error_info()
    	{
    		cout << "The queue size is " << queueSize << endl;
    	}
    };
    #endif

    寻找最短路径的算法思路:

    从上面的迷宫中,找一条从入口到出口的最短路径,要有两个过程:

    1. 一个是距离标记过程

    2. 另一个是路径标记过程

    在距离标记过程中,把能从入口到达的相邻位置标记为1,然后把从编号为1可到达的相邻位置标记为2(表示与入口相距为2),直到到达出口或者没有可标记的相邻位置为止。

    在路径标记过程中,从出口开始,首先移动到比出口的编号小1的位置,再从当前位置移动到比其编号小1的位置上,直到到达起点为止,这便是最短的路径

    3.按照上述思路编写代码实现:

    main.cpp

    #include <iostream>
    #include "E:\back_up\code\c_plus_code\dequeue\external_file\queue.h"
    using namespace std;
    
    // 迷宫
    template<typename T>
    void print_array(T **a, int size)
    {
    	for(int i=0; i<size; i++)
    	{
    		for(int j=0; j<size; j++)
    		{
    			cout << a[i][j] << " ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    }
    
    
    class position    // 存储位置坐标 
    {
    	public:
    	int row;
    	int col;
    	position()
    	{
    		row = 0;
    		col = 0;
    	}
    	
    	position(int row, int col)
    	{
    		this->row = row;
    		this->col = col;
    	}
    	
    	/*
    	void add_offset(position& ps)
    	{
    		row += ps.row;
    		col += ps.col;
    	}
    	*/
    	 
    }; 
    
    
    void findPath(int** map, int mapSize=10)
    {
    	// 这里默认起始点为(0,0),终点为(9,9)
    	
    	// 给地图添加围墙:
    	int** new_map = new int*[mapSize+2];
    	for(int i=0; i<mapSize+2; i++)
    	{
    		new_map[i] = new int[mapSize+2];
    	} 
    	for(int i=0; i<mapSize+2; i++)
    	{
    		for(int j=0; j<mapSize+2; j++)
    		{	
    			if(i==0 || i==mapSize+2-1)
    			{
    				new_map[i][j] = 1;  // 增加行围墙 
    			}
    			else if(j==0 || j==mapSize+2-1)   //增加列围墙 
    			{
    				new_map[i][j] = 1;
    			}
    			else  // 保存地图 
    			{
    				new_map[i][j] = map[i-1][j-1]; 
    			} 
    			
    		}
    	}
    	
    	// print_array(map, mapSize);
    	cout << "原始地图: " << endl;
    	print_array(new_map, mapSize+2);
    	
    	// 初始化偏移量
    	position offset[4];
    	// 向右偏移  index=0 
    	offset[0].row = 0;
    	offset[0].col = 1; 
    	// 向下偏移  index=1
    	offset[1].row = 1;
    	offset[1].col = 0;
    	// 向左偏移   index=2
    	offset[2].row = 0;
    	offset[2].col = -1;
    	// 向上偏移   index=3
    	offset[3].row = -1;
    	offset[3].col = 0; 	
    	
    	position current_position(1,1);   // 初始化当前位置
    	position end_position(10,10);
    	new_map[current_position.row][current_position.col] = 2;  // 这里距离标记从2开始,实际距离等于标号-2
    	int direction_number = 4;   // 一个方格相邻位置的个数 
    	position neighbor;
    	queue<position> q;    // 队列,用于存放标记的位置 
    	while(true)
    	{
    		// 给相邻位置做标记
    		for(int i=0; i<direction_number; i++)
    		{
    			neighbor.row = current_position.row + offset[i].row;
    			neighbor.col = current_position.col + offset[i].col;
    			if(new_map[neighbor.row][neighbor.col]==0)  // 可标记的位置
    			{
    				new_map[neighbor.row][neighbor.col] = new_map[current_position.row][current_position.col]+1; // 标记 
    				if(neighbor.row==end_position.row && neighbor.col==end_position.col)
    				{
    					break;   // 标记完成 
    				} 
    				q.push(neighbor); 
    			} 
    		}
    		if(neighbor.row==end_position.row && neighbor.col==end_position.col)
    		{
    			break;   // 到达 
    		}
    		
    		if(q.empty())    // 迷宫无解; 
    		{
    			cout << "The puzzle has no solution" << endl;
    			return;
    		}
    		
    		current_position = q.front();
    		q.pop(); 
    	}
    	//cout << "标记完的矩阵: " << endl; 
    	//print_array(new_map, 12); 
    	
    	// 构造路径;
    	int pathLength = new_map[end_position.row][end_position.col]-2;  // 路径的长短 
        // position* path = new position[pathLength];
    	
    	queue<position> q_path;   // 存储路径 
    	current_position =  end_position;   // 从终点回溯
    	for(int i=pathLength-1; i>=0; i--)
    	{
    		// path[i] = current_position;   
    		q_path.push(current_position);    // 当前的位置放入队列中 
    		for(int j=0; j<direction_number; j++)
    		{
    			neighbor.row = current_position.row + offset[j].row;
    			neighbor.col = current_position.col + offset[j].col;
    			if(new_map[neighbor.row][neighbor.col] == i+2)
    			{
    				break;
    			}
    		} 
    		//测试 
    		// cout << "current position: " << current_position.row << ',' << current_position.col << endl;
    		current_position = neighbor;	
    	} 
    	
    	/*    测试代码 
    	position tmp; 
    	while(!q_path.empty())
    	{
    		tmp = q_path.front();
    		cout << "path: " << tmp.row << "," << tmp.col << endl;
    		q_path.pop();
    	}
    	*/
    	
    	/*   测试代码 
    	for(int i=0; i<pathLength; i++)
    	{
    		cout << "path: " << path[i].row << "," << path[i].row << endl;
    	}
    	*/
    	
    	
    	
    	// 输出结果 
    	char** result = new char*[mapSize+2];    // 创建一个新的矩阵保存可视化结果 
    	for(int i=0; i<mapSize+2; i++)
    	{
    		result[i] = new char[mapSize+2];
    	}
    	// 初始化:
    	position tmp;
    	while(!q_path.empty())
    	{
    		tmp = q_path.front();
    		result[tmp.row][tmp.col] = '*';
    		q_path.pop();
    	} 
    	
    	for(int i=0; i<mapSize+2; i++)
    	{
    		for(int j=0; j<mapSize+2; j++)
    		{
    			if(result[i][j] != '*' && new_map[i][j]==1)
    			{
    				result[i][j] = '1';
    			}
    			if(result[i][j] != '*' && (new_map[i][j]==0 || new_map[i][j]>1))
    			{
    				result[i][j] = '0';
    			}
    		}
    	}	
    	
    	// 输出迷宫路径
    	cout << "最短路径: " << pathLength << endl; 
    	cout << "迷宫路径如下所示: " << endl;
    	print_array(result, mapSize+2); 
    	
    } 
    
    
    
    int main(int argc, char *argv[])
    {	
        int map_size = 10;
        int input_map[10][10] = {
       	                   {0,1,1,1,1,1,0,0,0,0},
       	                   {0,0,0,0,0,1,0,1,0,0},
    					   {0,0,0,1,0,1,0,0,0,0},
    					   {0,1,0,1,0,1,0,1,1,0},
    					   {0,1,0,1,0,1,0,0,0,0},
    					   {0,1,0,0,0,1,0,1,0,1},
    					   {0,1,0,0,0,1,0,1,0,1},
    					   {1,0,0,0,0,0,0,1,0,0},
    					   {0,0,0,0,1,1,1,1,0,0} 
                          };
        // 数据转换 
    	int** map_in = new int*[map_size];
    	for(int i=0; i<map_size; i++)
    	{
    		map_in[i] = new int[map_size];
    	}
    	for(int i=0; i<map_size; i++)
    	{
    		for(int j=0; j<map_size; j++)
    		{
    			map_in[i][j] = input_map[i][j];
    		}
    	}
    	
    	// 将原始地图转换为指针的形式
    	findPath(map_in, map_size);    
    	return 0;
    }
    

    算法的运行结果如下图所示:

    ---------------------------------------------------end----------------------------------------------------------

    展开全文
  • 数据结构预算法迷宫问题 哈尔滨工业大学 金字塔的小蜗牛 一问题描述 编写一个程序随机生成一个 20 x 20 的迷宫并找到一条从入口到出口的 路线 要求 (1) 迷宫大小可变模式随机 (2)迷宫没有通路时给出警告有通路时任给...
  • 根据书中的伪代码实现的迷宫求解,但是并不是最优解,适合刚开始学栈的同学参考 #include #include #include #include #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASINLE -1 #...
  • 迷宫问题——栈实现(C语言)(数据结构与算法

    千次阅读 多人点赞 2020-11-08 16:26:30
    本文用栈解决迷宫问题,采用C语言实现,包括问题介绍、算法简介、求解过程、代码实现、结果展示。并附有完整代码。

    前言

    本文用栈解决迷宫问题,采用C语言实现,包括问题介绍、算法简介、求解过程、代码实现、结果展示。并附有完整代码。


    本文完整代码:
    https://pan.baidu.com/s/1r24R6mTlGHxUkEezWm4BjQ

    提取码:2bbE

    一、迷宫问题

    概括来说,迷宫问题就是在一个封闭空间里,事先不知道这个封闭空间的内部结构,经过个方向试探,从而找到一个出口。假设有个机器人放置在这个封闭空间的入口处:

    • 迷宫用一个二维数组表示,0表示可以通行,1表示不可以通行
      构成迷宫为类似二维数组
      在这里插入图片描述
      (可以看到这个数组周围全是1,这里1表示不同,相当于迷宫的四周,这样可以保证机器人不会在搜寻过程中不会离开迷宫,当给定的迷宫没有边界时,建议自己添加上)
    • 在任意给定时刻,机器人只能在上下左右四个方向上移动1步
    • 机器人只能移动到没有障碍物的位置即0的位置,且不可以离开迷宫
    • 机器人不可以重复走某点
    • 机器人应该搜索从起始位置到目标位置的路径,直到找到一个或者耗尽他所有可能性

    二、问题分析

    1.位置表示

    由于迷宫构成是一个二维数组,我们可以采用坐标的形式 ( x , y ) (x,y) (x,y)来表示机器人的位置,为了方便代码实现,我将入口出的位置规定为(1,1)标蓝的位置为(1,1)如下图所示:
    在这里插入图片描述

    2.方向探寻

    规定机器人探寻的方向为四个

    dierctincXincY
    001
    110
    20-1
    3-10

    我们用incX、incY分别表示x、y方向上的增量表示如果机器人往这个方向上移动其位置坐标将会发生如上的变化。可以看到上面这个方向是遵循右下左上的原则,我们就可以定义一个结构体数组分别保存incX、incY这两个变量,对其实例化后即可实现方向的增量表示。

    //定义一个结构体表示方向的增量
    typedef struct{
    //x,y方向的增量
    int incX,incY;
    }Direction;
    

    实例化:

        Direction direct[4]= {{0,1},{1,0},{0,-1},{-1,0}};
    

    3、算法实现过程

    双层循环控制,内层循环控制机器人方向探寻过程,依次探寻四个方向,外层循环保证机器人进行回溯时退栈不为空。

    1. 机器人从入口处(1,1)出发,开始按照右下左上的方向顺序进行搜索,判断四个方向上是否有路可走,这里实现过程可以利用一层循环实现,依次遍历方向搜寻的四个方向,有路可走的含义就是机器人目前所处的位置上下左右四个方向是不是有为0的取值,有的话就证明机器人目前所处的位置不是死路,是能够前进的。
    2. 因此把目前的位置和前进的方向这三个变量进行入栈操作。
    3. 入栈完成后进行位置更新。要不这个已经走过的位置用-1替换,不再用0或者1表示。
    if(maze[line][col]==0)
                {
                    temp.x=x;
                    temp.y=y;
                    temp.di=di;
                    push(&S,temp.x ,temp.y ,temp.di);
                    x =line;
                    y =col;
                    maze[line][col]= -1;
    
    1. 当然,如果四个方向都搜寻完,一位置这一层循环跳出了,那这样就是回溯算法的核心思想,这是机器人目前所处的位置是不会入栈的,反而会执行退栈操作,返回到前一个位置,我们之前保存的其前进的位置就有用了,用di这个方向变量同时接受收当时保存的位置,位置更新后再次进入方向搜索的循环,这样不需要重复搜索原来已经搜索过的地方,因为原来搜索过的地方是走不通的,如果入栈时不保存原来的位置就会陷入死循环。
        while(!IsEmptyStack(&S))
        {
            pop(&S,&(temp.x),&(temp.y),&(temp.di));
            x = temp.x;
            y = temp.y;
            di = temp.di +1;
            while(di <4)
            {
                line = x+ direct[di].incX;
                col = y + direct[di].incY;
                if(maze[line][col]==0)
                {
                    temp.x=x;
                    temp.y=y;
                    temp.di=di;
                    push(&S,temp.x ,temp.y ,temp.di);
                    x =line;
                    y =col;
                    maze[line][col]= -1;
                    if(x ==M && y == N)
                        {
                            //由于栈先入后出的特性这里重新定义一个栈目的就是能够正序输出其坐标
                            while(!IsEmptyStack(&S))
                            {
    
                                pop(&S,&(temp.x),&(temp.y),&(temp.di));
                                push(&H,temp.x ,temp.y ,temp.di);
                            }
                            while(!IsEmptyStack(&H))
                            {
                              pop(&H,&(temp.x),&(temp.y),&(temp.di));
                              printf("(%d,%d),direct: %d\n",temp.x,temp.y,temp.di);
                            }
    
                            return 1;
                           // int e1,e2,e3;
                            //GetTop(&S, &e1,&e2,&e3 );
                           // printf("%d",e1);
    
                        }
                    else di =0;
                }
                else
                    di ++;
            }
        }
    
    
    
    1. 既然有退栈的操作,我们还要有一层循环,去判断栈是否为空,如果栈为空还没有到终点,表示这个迷宫无解,我们也要对这个结果做出反馈。
    2. 机器人搜索道路的终点应该是,机器人当前的位置坐标为最后的出口位置,即表示成功走出迷宫。
    3. 成功走出迷宫后,要对其路程进行输出,由于栈先进后出的特点,栈顶保存的位置坐标是机器人最后的走的位置,这里我采用的方法是重新定义一个栈,原有栈的结果依次出栈入新栈,打印的时候让新栈依次出栈
     while(!IsEmptyStack(&S))
                            {
    
                                pop(&S,&(temp.x),&(temp.y),&(temp.di));
                                push(&H,temp.x ,temp.y ,temp.di);
                            }
                            while(!IsEmptyStack(&H))
                            {
                              pop(&H,&(temp.x),&(temp.y),&(temp.di));
                              printf("(%d,%d),direct: %d\n",temp.x,temp.y,temp.di);
                            }
    
    

    二、遇到的问题与解决方案

    1.结构体数组入栈的问题

    1. 栈中需要保存位置坐标x、y以及从目前该位置移动至下一个位置的方向,保存这个方向的目的就在于走错路进行退栈。无需要四个方向重新遍历,在原有基础上查找为走过的方向即可。栈中保存的不再是一个数而应该是三个数,栈顶指针top更新时不可以简单的top++,理解也很简单这三个数分配的空间定义的一个结构体抽象数据类型用到的空间,具体是多少我们很难估计,基于此考虑利用双链表实现我们在定义保存当前位置坐标与方向这个结构体时定义同样类型的指针,分别指向他的前一个节点与后一个节点,这样在更新栈顶指针所指位置时,直接将next指针传给top就能顺利完成出栈与入栈。而对于出栈一样的操作,数据出栈后,只需要把parent指针的内容传给top。由此我们可以看出,栈的实现本质上变成了双向链表的操作。分别对应其入栈出栈。简单的画了一下栈内各结点的连接过程:
      在这里插入图片描述

    2. 当我们考虑好结构体入栈出栈的具体实现方式,就要改变原来初始化的问题。进行栈的初始化,我采用的是提前动态申请部分空间,除了空间的申请更要构建好节点之间的关系,即能够正确找到next节点与parent节点。为了能够正确描述节点之间的关系选择采用循环申请的动态空间的方式。为了保证数据能够顺利入栈,栈顶指针需要指向下一个放入数据的空间,因此让栈顶指针等于栈底指针,初始化完成,得到一个空栈。

    Status InitStack(SeqStack* stack)
    {
    	//开辟空间
    	stack->base=stack->top = (EleType*)malloc( sizeof(Box));
    	int i =0;
    	for(i=0; i <50;i++)
        {
          stack->top->next = (EleType*)malloc( sizeof(Box));
          stack->top->next->present = stack->top;
          stack->top = stack->top->next;
        }
    	stack ->top = stack ->base;
    	if (!stack->base)
    	{
    		exit(0);
    	}
    	stack->stackSize = STACK_INIT_SIZE;
    	return OK;
    }
    

    二、结果展示

    在这里插入图片描述

    展开全文
  • 递归的概念 **简单的说:**递归是方法自己调用自己,每次调用时传入...3)如果方法中使用的是引用类型变量(比如数组),就会共享引用类型的数据讲 4)递归必须向退出递归的条件逼近,否则就是无限递归,出现Stackfl...

    递归的概念

    **简单的说:**递归是方法自己调用自己,每次调用时传入不同的变量。递归有助于编程者解决复杂的问题,让代码变得简洁

    递归需要解决的重要规则

    1)执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
    2)方法的局部变量是独立的,不会互相影响
    3)如果方法中使用的是引用类型变量(比如数组),就会共享引用类型的数据讲
    4)递归必须向退出递归的条件逼近,否则就是无限递归,出现StackflowError,死递归。
    5)当一个方法执行完毕 或者 遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

    递归-迷宫问题

    在这里插入图片描述
    说明:
    小球得到的路径,和程序员设置的找路策略有关。即:找路的上下左右的顺序相关
    再得到小球路径时,可以先使用(下右上左),再改成(上右下左),看看路径是不是有变化
    测试回溯现象
    思考: 如何求出最短路径?

    Python代码

    '''
        // 使用递归回溯给小球找路
        // 说明:
        // map表示地图
        // 起点为(1,1)
        // 终点为(6,5)
        // map[i][j]=0为空,=1为墙,=2表示可以走,=3表示路走不通
        // 前进方向策略:下-》右->左-》上,如果走不通,就回溯
        '''
    def setWay(map,i,j):
        if map[6][5]==2:
            return True
        else:
            if map[i][j]==0:
                map[i][j]=2
                if setWay(map,i+1,j):
                    return True
                elif setWay(map,i,j+1):
                    return True
                elif setWay(map,i-1,j):
                    return True
                elif setWay(map,i,j-1):
                    return True
                else:
                    map[i][j]=3
                    return False
            else:
                return False
                
    # 先创建一个二维数组,模拟迷宫    
    map = [[0 for col in range(7)] for row in range(8)]
    for i in range(7):
        map[0][i]=1
        map[7][i]=1
    for i in range(8):
        map[i][0]=1
        map[i][6]=1
    
    map[3][1]=1
    map[3][2]=1
    map[5][3]=1
    map[5][4]=1
    map[5][5]=1
    
    #输出迷宫
    print("原来的迷宫----------")
    for i in range(8):
        for j in range(7):
            print("%2d"%map[i][j],end='')
        print()
    
    setWay(map,1,1)
    
    print("找到路径后:2为走过的点,3为走过但走不通的点")
    for i in range(8):
        for j in range(7):
            print("%2d"%map[i][j],end='')
        print()
    
    
    
    展开全文
  • 文章目录递归调用机制简单的递归使用递归能解决的问题和规则递归-迷宫问题思路分析:代码如下: 递归调用机制 简单地说:递归就是方法自己调用自己,每次调用时传入不同的变量,递归有助于编程者解决复杂的问题,...
  • #资源达人分享计划#
  • 数据结构与算法一,递归1,简介: 一,递归 1,简介: 递归: 自己调用自己,每次传入的参数不同; 递归调用规则: 当程序执行到一个方法时,会在栈中开辟一个新的受保护的栈空间; 方法的局部变量是独立的,不会...
  • 01-001数据结构的概念和基本术语、抽象数据类型的表示实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示实现、线性表的基本操作 02-003单链表的创建操作、加工型...
  • 韩顺平JAVA数据结构与算法、跟着写的代码 当然,附带有测试github的作用 src文件夹才是源码 目录结构 主要目的是学习java的数据结构 重点是算法 list list下有双向链表、单向循环链表约瑟夫问题、单向链表 queue ...
  • 包含了各种数据结构算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
  • 数据结构实验之用栈解决迷宫问题
  • 迷宫问题 迷宫问题的特点 存在一集可能位置一些位置相互连通一步可达 一个位置可能连通若干位置出现向前探查的多种可能有分支 目标是找到一条路径而不是找所有的能行路径 为了找到路径可能需要逐一探查不同的可能...
  • 主要介绍了C语言 数据结构中求解迷宫问题实现方法的相关资料,需要的朋友可以参考下
  • 数据结构与算法分析》课程设计——迷宫问题 - 刷子zz - 博客园 一、问题描述 问题中迷宫可用方阵[m,n]表示,0表示能通过,1表示不能通过。若要从从左上角[1,1]进入迷宫,设计算法,寻求一条从右下角 [m,n] ...
  • 数据结构迷宫算法

    2014-03-07 21:14:23
    学习数据结构时候编写的迷宫算法, 欢迎批评指正相互学习!
  • 数据结构与算法之走迷宫

    千次阅读 2017-07-10 20:21:16
    数据结构与算法 Java实现走迷宫
  • 按照《数据结构算法与应用C++语言描述》第九章栈的思路来实现解法。 迷宫内部主要有四个函数。welcome函数是欢迎界面,inputMaze函数是输入迷宫,findPath是寻找迷宫解法,outputPath是输出迷宫解法。 #include &...
  • -回溯算法 回溯算法是递归算法的一种特殊形式。回溯算法的基本思想是:对一个包括有很多个结点,每个结点有若干个搜索分支的问题,把原问题分解为对若干个子问题求解的算法;当搜索到某个结点、发现无法再继续搜索...
  • 本文实例讲述了Python数据结构与算法之图的广度优先深度优先搜索算法。分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从...
  • 数据结构与算法 第章 录页录页 概论 第1章概论 问题求解 数据结构及抽象数据类 算法的特性及分类 算法的效率度量 数据结构的选择和评价 2 张铭 数据结构与算法 第章 录页录页 1.1 问题求解 问题求解 概论 编写计算机...
  • 一个二维列表表示迷宫(0表示通道,1表示围墙),给出算法,求一条走出迷宫的路径 1、使用栈——深度优先搜索 回溯法 一条路走到黑,不行就回退 思路:从一个节点开始,任意找下一个能走的点,当找不到能走的点时...
  • 数据结构与算法----迷宫求解课程设计.doc
  • 数据结构与算法

    万次阅读 多人点赞 2020-05-19 16:39:12
    数据结构,是指相互之间存在一种或多种特定关系的数据关系的集合,用计算机存储、组织数据的方式。 数据结构分为逻辑结构、物理结构和数据的运算三大部分。 二、为什么要学数据结构 1、因为数据结构作为计算机...
  • 问题:如上图所示,通过递归算法,计算出从A点到B点的路线。 代码示例 public class MiGongTest { public static void main (String[] args) { //创建迷宫 1为墙,0为路的像素 int[][] map = { { 1, 1, 1, 1, 1...
  • 本文实例讲述了Python数据结构与算法之图的广度优先深度优先搜索算法。分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,441
精华内容 4,576
关键字:

数据结构与算法迷宫

数据结构 订阅