迷宫问题问题描述：

栈的实现在这篇博客中：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----------------------------------------------------------

前言

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

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

提取码：2bbE

一、迷宫问题

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

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

二、问题分析

1.位置表示

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

2.方向探寻

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

我们用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;

5. 当然，如果四个方向都搜寻完，一位置这一层循环跳出了，那这样就是回溯算法的核心思想，这是机器人目前所处的位置是不会入栈的，反而会执行退栈操作，返回到前一个位置，我们之前保存的其前进的位置就有用了，用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 ++;
        }
    }

6. 既然有退栈的操作，我们还要有一层循环，去判断栈是否为空，如果栈为空还没有到终点，表示这个迷宫无解，我们也要对这个结果做出反馈。
7. 机器人搜索道路的终点应该是，机器人当前的位置坐标为最后的出口位置，即表示成功走出迷宫。
8. 成功走出迷宫后，要对其路程进行输出，由于栈先进后出的特点，栈顶保存的位置坐标是机器人最后的走的位置，这里我采用的方法是重新定义一个栈，原有栈的结果依次出栈入新栈，打印的时候让新栈依次出栈

 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;
}

二、结果展示

递归的概念

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

递归需要解决的重要规则

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()