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

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

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

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

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

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

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

findRoad.cpp

//迷宫求解问题思路
//1.用一个矩阵来表示迷宫，即n*m数组
//用穷举法实现；即从入口出发，顺着某一个方向向前探索，若能走通，则继续往前走；
//若到了某一点走不通，则标记该点为不可达
//否则原路返回,换一个方向再继续探索
//具体的请看算法解释
#include
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 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
using namespace std;
//const int MAX=100；//栈最大长度值为100，用数组实现栈
//写成模板类是为了方便我以后使用
template
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
#include
#include
#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

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

1 0 1 0 1
0 0 1 0 0
0 0 1 0 0
0 0 1 0 1
1 0 0 0 0

原文链接

赏

感谢支持

支付宝

微信