nullnull迷宫问题迷宫问题迷宫问题主要内容
1．问题分析
2．递归算法
3．非递归算法1．问题分析1．问题分析1．问题分析1．问题分析迷宫求解
这是一个找出口的问题。自相似性表现在什么地方？ 每走一步的探测方式。
由于计算机很傻，只能通过穷举方式找出口，怎么找法？沿着一个方向走下去，如果走不通，则换个方向走；四个方向都走不通，则回到上一步的地方，换个方向走；依次走下去，直到走到出口。
1．问题分析1．问题分析描述迷宫：
1、设置迷宫为二维数组，数组的值是
-1：代表墙
0： 代表未走过的路径
1：代表走不通的路径
2：代表路径
1．问题分析1．问题分析1．问题分析1．问题分析2、设置搜索方向顺序是东、南、西、北(x,y)(x-1,y)(x,y-1)(x,y+1)(x+1,y)东北2．递归算法2．递归算法明确递归函数的意义
每一步的走法
int next(int arr[][10],Point cur, Point end)；
迷宫求解迷宫求解每走一步：
1、如果当前位置=出口，结束
2、否则：
假设当前位置为路径；
如果东面未走过：向东走一步
如果南面未走过：向南走一步
如果西面未走过：向西走一步
如果北面未走过：向北走一步
设置当前位置走不通，回溯nullint next(int arr[][10],Point cur,Point end)
{
if((cur.x==end.x) && (cur.y==end.y)) return 1;
else
{
arr[cur.x][cur.y] = 2;
if(arr[cur.x+1][cur.y]==0) //东
{
Point t;
t.x =cur.x+1;
t.y=cur.y ;
if(next(arr,t,end)) return 1;
}
if(arr[cur.x][cur.y+1]==0) //南
{
Point t;
t.x =cur.x;
t.y=cur.y+1;
if(next(arr,cur,end)) return 1;
}
… //西 …//北
arr[cur.x][cur.y] = 1;
return 0;
}3．非递归算法3．非递归算法程序步骤：
1、当前位置入栈
2、判断下一步是否可通，“可通”则返回步骤1; “不可通”，换方向继续探索;
3、若四周“均无通路”，则当前位置出栈，从前一位置换方向搜索。
nullvoid MasePath(int arr[][10],Point start,Point end)
{
Stack
PointStack;
Point P=start;
arr[P.x][P.y] = 2;
do{
PointStack.Push(P);
if (arr[P.x][P.y+1]==0) arr[P.x][++P.y] = 2;
else if (arr[P.x+1][P.y]==0) arr[++P.x][P.y] = 2;
else if (arr[P.x][P.y-1]==0) arr[P.x][--P.y] =2;
else if (arr[P.x-1][P.y]==0) arr[--P.x][P.y] = 2;
else
{
P = PointStack.Pop();
arr[P.x][P.y] = 1;
P = PointStack.Pop();
}
}while ((P.x!=end.x) || (P.y!=end.y));
}辅助函数辅助函数//打印迷宫
void PrintPath(int arr[][10])
{
for (int i=0;i<10;i++)
{
for (int j=0;j<10;j++)
{
if (arr[i][j]==-1) cout<<"■";
else if (arr[i][j]==2) cout<<" *";
else cout<<"□";
}
cout<
本文档为【迷宫问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483