&>&&>&&>&&>&迷宫求解输入一个任意大小的迷宫数据，求出一条走出迷宫的路径，并将路径输出。
迷宫求解输入一个任意大小的迷宫数据，求出一条走出迷宫的路径，并将路径输出。
上传大小：4KB
设计要求：输入一个任意大小的迷宫数据，求出一条走出迷宫的路径，并将路径输出。
综合评分：5（3位用户评分）
所需积分：10
下载次数：32
审核通过送C币
创建者：fireblue1990
创建者：ljheee
课程推荐相关知识库
上传者其他资源上传者专辑
课程资源热门标签
VIP会员动态
android服务器底层网络模块的设计方法
所需积分：0
剩余积分：720
您当前C币：0
可兑换下载积分：0
兑换下载分：
兑换失败，您当前C币不够，请先充值C币
消耗C币：0
你当前的下载分为234。
迷宫求解输入一个任意大小的迷宫数据，求出一条走出迷宫的路径，并将路径输出。
会员到期时间：
剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
wenfengwangzhe
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：迷宫一题，我卡住了一个星期，求帮助
（migong.pas/c/cpp）
【问题描述】
小刚在迷宫内，他需要从A点出发，按顺序经过B,C,D……，到达最后一个点，再回到A点。迷宫内有些障碍，问至少走几步。
输入文件migong.in共n+1行。
第一行有三个数n，m表示迷宫有n行，m列。
第2行到第n+1行，每行m个字符，可能是’A’..’Z’,’2’,’0’ 其中，2表示障碍，0表示可以走。’A’..’Z’也可以走。
输出文件migong.out共1行，就是至少走几步可以按规定走完，如果不行，输出“Impossible”
代码如下：
#include&fstream&
ifstream fin(&migong.in&);
ofstream fout(&migong.out&);
const int dx[4]={-1,1,0,0};
//上下左右扫描
const int dy[4]={0,0,-1,1};
int visited[1];
int sum=0;
struct qtype
}quene[10000];
bool bfs(int x1,int y1, char goal);
int main()
int x2,y2=0;
char goal1='A';
fin&&m&&n;
for (int i=1;i&=m;++i)
for (int j=1;j&=n;++j)
fin&&d[i][j];
if (d[i][j]&='A' && d[i][j]&='Z')
if (d[i][j]=='A')
{x2=i; y2=j;}
if (d[i][j]&goal1) goal1=d[i][j];
//record the position of 'A' and max later's.
if (x2==0) fout&&&Imposibble&;
if (bfs(x2,y2,goal1))
fout&& else fout&&&Imposibble&;
///////////////////////////////////////
bool bfs(int x1,int y1, char goal)
//出发状态
int head=0, tail=0;
quene[head].x=x1;
quene[head].y=y1;
char next='B';
memset(visited, 0, sizeof(visited));
visited[x1][y1]=1;
while (head&=tail)
//如果队列非空
for (int i=0; i&=3; ++i)
p= quene[head].x + dx[i];
q= quene[head].y + dy[i];
if (p&0 && p&=m && q&0 && q&=n && !visited[p][q] && d[p][q]!='2')
quene[tail].x=p;
quene[tail].y=q;
visited[p][q]=1;
if (d[p][q]==next)
{ if (next==goal)
memset(visited, 0, sizeof(visited));
if (next==goal)
else {++ ++}
虽然程序功能是从A走到目标点，没有符合题目要求，但从A走到目标点我也不能实现，求解救啊，困了我一个星期了。
& 2012 - 2016 &
&All Rights Reserved. &
/*爱悠闲图+*/
var cpro_id = "u1888441";求迷宫从入口到出口的所有路径是一个经典的程序设计问题，求解迷宫，通常采用的是“穷举+回溯”的思想，即从入口开始，顺着某一个方向出发，若能够走通，就继续往前走；若不能走通，则退回原路，换一个方向继续向前探索，直到所有的通路都探寻为止。因此本文依据这种“穷举+回溯”的思想，设计一个求解迷宫的程序。
1 问题分析
为了保证在任何位置上都能够退回原路，显然需要使用一个先进后出的数据结构来保存已经探寻过的位置，因此在程序求解迷宫路径的过程中采用栈这种数据结构。
迷宫是一个二维地图，其中含有出口和入口，障碍点和通道，因此程序采用一个二位数组map来表示，其中，二维数组值所代表的含义如下：
需要注意的是，最后求解出来的通路，必须要是一条简单路径，即在求得的路径上不能重复出现同一通道快。下面简述一下程序的求解过程。
将“在搜索过程中某一个时刻所在迷宫地图中的位置“记为“当前位置”，那么求解迷宫路径算法的基本思想是：若“当前位置”可通行，那么将“当前位置”纳入求解路径中（压到栈中），并朝“下一个位置”继续探索，即把“下一位置”切换到“当前位置”，如此重复下去，直到找到出口；如果当前位置不可以通行，则顺着来的方向退回到“前一个通道位置”，然后再朝着其他方向探索下去；如果该通道块的4个方向（东西南北）都不可通，那么就在该路径（栈）中删除该通道位置（删除栈顶元素），再继续退回到“前一个通道位置”继续探索，即再获取栈顶元素作为“当前位置继续上述的重复探索。
2 算法描述
根据对迷宫问题的分析，求迷宫中一条从入口到出口的路径算法描述如下：
设定入口位置为当前位置。
if（当前位置是可通行且是没有被走过的通道块 ）（分支1）
2.1 将当前位置压到栈中。
2.2 若当前位置是出口，则程序结束，返回路径栈。
2.3 若当前不是出口，则切换当前位置为当前位置东边的通道块，返回2继续执行。
else（若当前位置不可通行）（分支2）
3.1 获取栈顶元素所在的位置，若该位置所在的相邻4个方向都被探索过了，则删除当前栈顶元素，获取新的栈顶元素，直到找到一个可通的相邻块位置或出栈至栈空再执行3.2步骤。
3.2 若栈顶元素所在的位置还有其他方向没有被探索过，则设定新的当前位置为栈顶元素的未被探索方向的相邻通道块。(方向访问顺序为顺时针即东南西北)
重复步骤2.
需要注意步骤2中的没有被走过的通道块,是指该通道块从来未压入栈中，否则求解的路径就不是一条简单路径，很可能导致一个死循环。
3 程序实现
程序采用c#语言对上述的算法描述进行了实现，代码如下。
3.1 通到块实体
class PathElement
public PathElement(int row, int col, int direcation)
this.Row =
this.Col =
this.Direction =
public int R//位置所在的行
public int C//位置所在的列
public int D//从此位置走向下一位置的方向,方向分为东0南1西2北3，默认东方向为初始方向
3.2 寻找简单路径
public static Stack&PathElement& FindPath(int[,] map, int startX, int startY, int endX, int endY)
Stack&PathElement& path = new Stack&PathElement&();
List&PathElement& visitedList = new List&PathElement&();//保存以通过的元素
PathElement curPosition = new PathElement(startX, startY, 0);
int tryCount = 0;
tryCount++;
if (Pass(curPosition, map) && (!Visited(curPosition, visitedList)))//当前位置能通过，且没被访问过
path.Push(curPosition);//加入路径
if (curPosition.Row == endX && curPosition.Col == endY)
visitedList.Add(curPosition);//该位置以被访问
curPosition = GetNextPosition(curPosition);//获取下一个当前位置,并更新该位置的下一个位置的方向
else//当前不能通过
if (path.Count != 0) //如何栈不为空
PathElement topElement = path.Peek();//获取栈顶元素
while (topElement.Direction == 4 && (path.Count & 1))//找寻一个可用的位置
path.Pop();
topElement = path.Peek();
if (topElement.Direction & 4)
curPosition = GetNextPosition(topElement);//获取下一个当前位置,并更新该位置的下一个位置的方向
} while (path.Count != 0);
3.3 辅助方法
/*获取下一个位置*/
private static PathElement GetNextPosition(PathElement curPostion)
PathElement nextPosition=
switch (curPostion.Direction)
nextPosition = new PathElement(curPostion.Row, curPostion.Col+1, 0);
nextPosition = new PathElement(curPostion.Row+1, curPostion.Col, 0);
nextPosition = new PathElement(curPostion.Row, curPostion.Col-1, 0);
nextPosition = new PathElement(curPostion.Row-1, curPostion.Col, 0);
curPostion.Direction++;
return nextP
/*是否为通道*/
private static bool Pass(PathElement curPosition, int[,] map)
int rowCount = map.GetLength(0);
int colCount = map.GetLength(1);
//边界判断
if (curPosition.Row &= 0 && curPosition.Row & rowCount && curPosition.Col &= 0 && curPosition.Col & colCount)
//障碍判断
if (map[curPosition.Row, curPosition.Col] == 2)
/*是否被访问*/
private static bool Visited(PathElement curPosition, List&PathElement& visitedList)
foreach (PathElement element in visitedList)
if (element.Row == curPosition.Row && element.Col == curPosition.Col)
该部分代码只是提供算法验证的可视化界面，与本文所探讨的算法实现没有多大的关系，程序的源代码可以在文章后面的链接进行下载。
界面所包含的功能：
能够编辑迷宫地图，单击实现障碍物的设计，双击去掉障碍物。
能够保存和载入地图。
能够通过该算法实现从迷宫入口到出口路径的生成和显示。
3.5 结果截图
1 地图的载入
2 路径寻找
“穷举+回溯”的思路还是很好理解，通俗的讲，就是选择一条道路一直走到黑，如果碰到前方有障碍，就退回来一步再换一个方向继续走，直到把所有可能的路都做完了。
利用“穷举+回溯”搜索路径，虽然简单，但是它属于一种盲目、机械的搜索算法，从3.5中的结果图中可以看出，该算法找出来的路径，显然不是最优的，走了许多的弯路。那么如何从迷宫的起点到终点找到一条最优的路径呢？请参考。
5 资源和参考资料
参考资料：严蔚敏《数据结构c语言版》
源代码下载：
阅读(...) 评论()藏地密码,第十级,卓木强巴和莫金遇到的迷宫里面,最后一题的答案.求解.(至少答案不是4)
本回答由提问者推荐
var sogou_ad_id=731547;
var sogou_ad_height=160;
var sogou_ad_width=690;每日一题064 | 来来来，走迷宫，走出去算你有本事！！！
这个迷宫入口和出口如箭头所示。有个限制规则是不能左转（相对于行进方向的“左”），也就是只能直走或者右转。大家来走走看吧，看多久能走出来？天！觉得好难！只许右转，不能左转！刚走出去，又要绕回来，怎样才能走到出口处啊？？请问，你走出来了嘛？用了多长时间？最速度的方式应该怎么走？来，带着你的路线扫描下方二维码，回复“064”，给你指明一条最的线路！当然如果你想把这题放在狠虐你的死党，我附议！【每日一题】往期内容请在微信平台下方右下角【宝宝】猛戳，就酱！
大家都在看
精彩内容随你high
&&&&&&&nbsp各位，各位，小长假要到啦！！！！我兴高采烈、得意洋洋、欢欣鼓舞、开心到不行！想立刻跑出去撒欢。所以，今天想来问问你，如果给你一张往返机票，你最想去哪？
Copyright (. All Rights Reserved.