用递归实现求一个迷宫是否有通路

今天终于把昨天下午没写出来的迷宫求是否有通路的cpp写出来了

使用递归实现的，不过算法的质量不怎么样，使用穷举法实现的。

在网上搜了一下，发现还有很多的更优的算法，哈哈，不过怎么说都是自己一个个地代码敲出来的。

特点是发现在linux下面调试真的有时候自己会崩溃，还好最终还是搞出来了。

哈哈，发上来给类似我这种的算法新手来一起分享一下；

路径就记录在栈里面，需要得出具体路径的可以小改一下就行了。

findRoad.cpp

//迷宫求解问题思路
//1.用一个矩阵来表示迷宫，即n*m数组
//用穷举法实现；即从入口出发，顺着某一个方向向前探索，若能走通，则继续往前走；
//若到了某一点走不通，则标记该点为不可达
//否则原路返回,换一个方向再继续探索
//具体的请看算法解释
#include <iostream>
using namespace std;
#include "stack.cpp"
struct box{
	bool status;//用于判断该处是否可通
	int direct;//用于标记在这里向哪个方向探索过了，
	//1234分别代表向左上右下的顺序探索,即顺时针方向
};
struct posType//用于记录某一点的坐标值
{
	int x;
	int y;
};
bool isEqueal(posType a,posType b)//跟arriived一样，不过名字变了而已
{
	if(a.x==b.x&&a.y==b.y)
		return true;
	return false;

}
bool arrived(posType start,posType end)//判断是否已经到达出口
{
	if(start.x==end.x&&start.y==end.y)
		return true;
	return false;

};
static mStack<posType> ms;//用于存放经过的路径
const int MAXLINE=5;//需要的时候再改
const int MAXROW=5;
bool findRoad(box (*arr)[MAXROW],posType start,posType end)//注意二维数组的指针表示
{
	int x=start.x;
	int y=start.y;
	if(arrived(start,end))//如果到达
		return true;
	//还会有下面这种情况
	//应该这样表达才对arr+start.x*MAXROW+start.y)->status
	//而不是(*arr+i)+j
	if((*arr+x*MAXROW+y)->status==false)//假设仅剩该点且该点四周都不可达，则路到了尽头！！
		return false;
	posType temp;
	if(ms.isEmpty())	//如果栈空
		ms.Push(start);		//将当前位置入栈
	else 	//判断是否是上一个点，避免重复入栈
	{
		ms.GetTop(temp);
		if(!isEqueal(temp,start))
			ms.Push(start);
	}
	
	
	switch((*arr+x*MAXROW+y)->direct)//检测往哪个方向走过了
	{
		//derect=0代表未向任何方向探索过，应向左探索
		//=1代表要向上探索
		case 0:if(y-1>-1&&(*arr+x*MAXROW+y-1)->status)//向左方探索，如果没有越界并且左方是可达的
			{
					//posType newStart(x-1,y);//以左方作为新起点
					posType newStart;
					newStart.x=x;
					newStart.y=y-1;
					(*arr+x*MAXROW+y)->direct=1;//应该是该点=1；该点探索过了而不是下一点
					//arr[newStart.x][newStart.y].direct=1;//探索的方向+1
					findRoad(arr,newStart,end);//以新起点开始探索
			}
			else//倘若数组越界了，或者左方不可达，则向上探索
			{
				(*arr+x*MAXROW+y)->direct=1;//令其=1，再递归调用
				findRoad(arr,start,end);//起点不变
			};break;
		case 1:if(x-1>-1&&(*arr+(x-1)*MAXROW+y)->status)//向上方探索，如果没有越界并且上方是可达的
				{
//					posType newStart(x,y-1);//以该起点作为新点
					posType newStart;
					newStart.x=x-1;
					newStart.y=y;
					(*arr+x*MAXROW+y)->direct=2;//应该是该点=1；该点探索过了而不是下一点
					//arr[newStart.x][newStart.y].direct=2;//探索的方向=2
					findRoad(arr,newStart,end);//以新起点开始探索
				}
				else//倘若数组越界了，则向上探索
				{
					(*arr+x*MAXROW+y)->direct=2;//令其=2，再递归调用,即指示其向下一个方向探索
					findRoad(arr,start,end);//起点不变
				};break;
		case 2:	if(y+1<MAXROW&&(*arr+x*MAXROW+y+1)->status)//向右方探索，如果没有越界并且右方是可达的
				{
					//posType newStart(x+1,y);//以该起点作为新点
					posType newStart;
//					newStart.x=x+1;
					newStart.x=x;//向右应该是y+1
					newStart.y=y+1;
					(*arr+x*MAXROW+y)->direct=3;
					//arr[newStart.x][newStart.y].direct=3;//探索的方向=3
					findRoad(arr,newStart,end);//以新起点开始探索
				}
				else//倘若数组越界了或者不可达，则向下探索
				{
					(*arr+x*MAXROW+y)->direct=3;//令其=3，再递归调用,即指示其向下一个方向探索
					findRoad(arr,start,end);//起点不变
				};break;
		case 3:	if(x+1<MAXLINE&&(*arr+(x+1)*MAXROW+y)->status)//向下方探索，如果没有越界并且下方是可达的
				{
					//posType newStart(x,y+1);//以该起点作为新点
					posType newStart;
					newStart.x=x+1;
					newStart.y=y;
					(*arr+x*MAXROW+y)->direct=4;
					//arr[newStart.x][newStart.y].direct=4;//探索的方向=3
					findRoad(arr,newStart,end);//以新起点开始探索
				}
				else//倘若数组越界了或者不可达，更改此点为不可达
				{
					(*arr+x*MAXROW+y)->direct=4;//令其=3，再递归调用,即指示其向下一个方向探索
					findRoad(arr,start,end);//起点不变
				};break;
		case 4:	(*arr+x*MAXROW+y)->status=false;//当四个方向都探索完了之后，均没有通路时，标记该点为不可达状态
				
				posType t;//将当前点出栈
				ms.Pop(t);//
				if(ms.isEmpty())//如果此时栈已经空了，说明没有路可以回头了，路不通
					return false;
				ms.Pop(start);//令上一路径为起点，递归找路
				findRoad(arr,start,end);
				break;
	};
};

stack.cpp

//用于实现栈的操作
#include <iostream>
using namespace std;
//const int MAX=100；//栈最大长度值为100，用数组实现栈
//写成模板类是为了方便我以后使用
template <class T>
class mStack{
	private:
		enum {MAX=1000};
		T arr[MAX];
		int Size;
		int top;//用于指示栈顶位置
	public:
		mStack(	)//构建空栈
		{
		  top=-1;//下标为-1则为空栈
		  Size=0;
		}
		bool isEmpty()
		{
			return top==-1;
		}
		bool isFull()
		{
			return top==MAX-1;
		}
		bool Push(T &item)
		{
			if(isFull())
			{
				cout<<"stack is full!"<<endl;
				return false;
			}
			//++top;
			//arr[++top]=item;
			arr[++top]=item;//因为下标从-1开始，使用前+1
			//cout<<"this "<<top<<" item push values is :"<<arr[top]<<endl;
			Size++;
			return true;
		}
		bool Pop(T &item)
		{
			if(isEmpty())
			{
				cout<<"stack is empty!"<<endl;
				return false;
			}
			item=arr[top--];//因为下标从-1开始，top指向当前最后一个元素,使用后-1
			//cout<<"this "<<top<<" item pop values is :"<<arr[top]<<endl;
			Size--;
			return true;
		}
		bool GetTop(T &item)
		{
			if(!isEmpty())
			{
				item=arr[top];
				return true;
			}			
			return false;
		}
		int size()
		{
			return Size;
		}

};

test.cpp

#include <fstream>
#include <cstdlib>
#include <ctime>
#include "all.cpp"
const int MAXL=5;
const int MAXR=5;

int main()
{
	ofstream fout;//("test1.txt");//,ios_base::app);//,ios_base::app);
	fout.open("test1.txt",ios_base::app);
	
	if(!fout.is_open())
		cerr<<"open failer!"<<endl;
	
	//box (*b)[MAXR];
	box (*b)[MAXR]=new box[MAXL][MAXR];
	ifstream fin("tx.txt");//从文件中读取迷宫
	if(!fin.is_open())
		cerr<<"fin open failure!"<<endl;

	for(int i=0;i<MAXLINE;i++)
		{
		for(int j=0;j<MAXROW;j++)
			{
				int num;
				fin>>num;
				//*(*(b+i)+j)=new box;
				if(num==1)
					(*(b+i)+j)->status=false;//给迷宫里的box赋值
					//(*(ar+i)+j)->status=false;
				else
					(*(b+i)+j)->status=true;
				
					(*(b+i)+j)->direct=0;
			}
		}
	
	fin.close();
	posType start;
	start.x=0;
	start.y=1;
	
	posType end;
	end.x=0;
	end.y=3;
	
	(*(b+start.x)+(start.y))->status=true;
	(*(b+end.x)+end.y)->status=true;
		
	for(int i=0;i<MAXLINE;i++)
	{
		
		for(int j=0;j<MAXROW;j++)
		{
			if((*(b+i)+j)->status)
				fout<<"0 ";
			else
				fout<<"1 ";
		}	
		fout<<endl;
	}	
	fout<<endl<<endl;
	fout.close();	
	

	if(findRoad(b,start,end))
		cout<<"has load!"<<endl;
	else
		cout<<"no load "<<endl;	
	
}

tx.txt

//可以自己设置迷宫路径和出发点以及出口

原文链接

24 2 月, 2016

royalchen

C/C++

0cpp

用递归实现求一个迷宫是否有通路

发表回复取消回复

用递归实现求一个迷宫是否有通路

发表回复 取消回复

发表回复取消回复