关于迷宫出路的问题,已经BFS遍历找到终点了,请问如何能求出路径 C++ 迷宫问题
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int mm=301;
int map[mm][mm];
int vis[mm][mm];
int dist[mm][mm];
int fa[mm][mm];
int last_dir[mm][mm];
//int dx[4]= {0,0,1,-1};
//int dy[4]= {1,-1,0,0};
//char name[]="";
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
char name[] = "UDLR";//???
int c[mm*mm];
int q[mm*mm];
int n,m,x,y;
void bfs(int x,int y)
{
int u=x*m+y;
vis[x][y]=1;
dist[x][y]=0;//起点距离初始化为0
fa[x][y]=u;//起点的祖先就是本身,用于起点寻找的标志
int front=0,rear=0;
q[rear++]=u;//入队
while(front<rear)
{
u=q[front++];//出队,节点拓展
x=u/m;
y=u%m;
for(int i=0; i<4; i++)//状态的转移
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]&&map[nx][ny])//条件判断
{
int v=nx*m+ny;
q[rear++]=v;//符合条件入队
dist[nx][ny]=dist[x][y]+1;//距离更新
fa[nx][ny]=u;//记录祖先
vis[nx][ny]=1;
last_dir[nx][ny]=i;//记录路径
}
}
}
}
void print(int x,int y)
{
int i=0;
for(;;)
{
int fx=fa[x][y]/m;
int fy=fa[x][y]%m;
if(fx==x&&fy==y)//满则该条件的点为起点
break;
c[i++]=last_dir[x][y];//有于是从终点开始寻找,将路径记录后反向输出
x=fx;
y=fy;
}
while(i--)
putchar(name[c[i]]);
//for(int j=0;j<i;j++)
//printf("%d ",c[j]);
}
int main()
{
int x1,y1,x2,y2;
int p,q;
while(scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2)==6)
{
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
scanf("%d",&map[i][j]);
bfs(x1,y1);
//打印路径
print(x2,y2);
//可求起点到任意点的最短距离
bool ret=false;
while(scanf("%d%d",&p,&q)==2)
{
if(p==0&&q==0)
{
ret=true;
break;
}
printf("%d\n",dist[p][q]);
}
if(ret) break;
}
return 0;
}
javaBFS求迷宫问题~
热心网友
以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
（1） 根据二维数组，输出迷宫的图形。
（2） 探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。
你的程序要接受一个命令行输入参数，这个输入代表了储存迷宫状态的文件名。比如你的程序是a.out，迷宫信息储存在maze1文件里面，那你程序的运行就需要是：
./a.out maze1 的格式
迷宫文件的格式：迷宫文件是一个文本文档格式，空格‘ ’表示可走路径，#表示墙（不能通过的地方）以及一个s字母和一个f字母分表表示起点和终点。并且迷宫满足一下性质：
1. 迷宫由#组成的墙完全包围，也就是说不可能出现从迷宫内一点走到外面的情况，四周一定都是墙的封闭图形。
2. s和f，起点与终点都在迷宫内部
3. 每一行最后一个#表示的墙结束以后是一个新的换行符。
4. 迷宫内没有不可到达的可行路径。（也就是任何一个空白符表示的一个点，一定有一条路径能到达）
5. 也没有U字形的迷宫。
具体情况看图例：
#######
# #############
######## ### # ###
# #f### ######### #
#s#### # # # ### #
### # ####### ### ### #
# #### # ### ###
# ########### ###
#### #####
###############
程序必须满足以下要求：
1. 读取迷宫
2. 通过计算迷宫相应表示的的矩阵（给你一个提示，就是二位数组就行了）
3. 打印出这个迷宫和相应的矩阵
4. 清空所有动态数据类型（不要造成内存溢出就行了）
通过某人的解题例子学习如何打印出矩阵和迷宫（你的原文没有附带）
迷宫数据结构：
你可以假设所有已知特测试都是合理的，但是你需要自己检查一下情况：
1. s和f是否仅出现一次？
2. s和f是否超出迷宫四面墙的范围？
3. 或者彻底没有s,f的情况
4. 以及不合法的字符（除了' ', #, s, f,
)
迷宫矩阵
计算一下两个矩阵
1. 迷宫有多少个分支路径？
2. 迷宫有多少条死路（无法从起点到达终点的路径）
顺带给你我个人的提示：
1. 路径算法要你自己去计算。。。。
2. 一点计算出路径总数过后，标记出合法的从起点到终点的所有可行路径，剩下来的迷宫矩阵的坐标中，没有被标记出来的点所构成的路径就是死路了。
挺有意思的，慢慢挣扎吧。
楼下给了你解释了，广度和深度都可以，但是考虑到你需要算具体分支数和死路，我觉得你用深度可能容易一点。你如果还不知道深度优先搜索的话，建议去看看基本搜索算法的教材，我不可能吧程序代码些给你。
大体思路
从s点出发开始搜索，如果当前的尝试可以到达f，则支路+1，如果当前路已经走到尽头并且不是f则死路+1
小型地图可以依赖于用简单递归解可以了，不必考虑太多。但是递归可能导致栈溢出，所以要小心使用。给你一个递归的简便算法：
char map[width][height];
bool visited[width][height];
int branchCount = 0;
int deadEndCount = 0;
bool findPath(int, int); // 递归函数 后面定义
int main(int argc, char** argv)
{
readMap(map, argv[1]); // 读地图的方法你就自己去写了，我就不多写了
for(int i = 0; i < width; i++)
for(int j = 0; j < height; j ++)
visited[i][j] = false; //初始化访问记录
for(int i = 0; i < width; i++)
for(int j = 0; j < height; j++)
if(map[i][j] == 's') findPath(i, j); // 如果起点坐标 是i,j，就从i,j开始搜索
return 0;
}
bool findPath(int i, int j) // 主菜
{
if(map[i][j] == '#' || visited[i][j]) return false; // 无效举动
visited[i][j] = true; // 标记当前坐标访问，这样就不用重复访问了
if(map[i][j] == 'f') {
branchCount++; //达到终点，合理解
return true; // 代表当前路径可行
}
if ( (map[i+1][j] == '#' || visited[i+1][j]) && (map[i - 1][j] == '#' || visited[i -1][j])
&& (map[i][j+1] =='#' || visited[i][j+1]) && (map[i][j-1] == '#' || visited[i][j-1]))
deadEndCount++; // 四面不通
if(!findPath(i + 1, j) && !findPath(i - 1, j) && !findPath(i, j+1) && !findPath(i, j -1)) {
return false; // 当前坐标属于不可行路径
}
\breturn true; // 当前坐标属于可行路径的一部分
}
以上算法可能找死路的部分我没有详细证明其正确性，可能会有错。但是用来找可行路径的部分应该是正确地。大体如果找死路的地方我也写错了，那你就自己再按照这个思路再走走看吧。
另外刚才我自己检查了一边，那个findPat h中的return true/false的代码其实没有多大意义，我只是草稿的时候放进去了，所以你定义findPath是void,然后直接return也没有关系。
如何确定点的位置
答：下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点u∈V，其色彩存储于变量color[u]中，结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u还没有被检索到)，则 π[u]=NIL，由算法算出的源点s和顶点u之间的距离存...
算法实现题 孤岛营救问题
答：分层图最短路径问题，用状压，用P位二进制表示当前获得的钥匙状态，建立2^P层图。每层图表示在当前钥匙状态下的地图，每获得一把钥匙进入新的一层，BFS求最短路即可，网络流24题中的14题，自己搜搜吧
用c++写一个迷宫程序
答：include<iostream> using namespace std;class T //定义描述迷宫中当前位置的结构类型 { public:int x; //x代表当前位置的行坐标 int y; //y代表当前位置的列坐标 int dir; //0:无效,1:东,2:南,3:西,4:北 };class LinkNode //链表结点 { friend class Stack;public:T...
有关圆明园的资料
答：最有名的“观水法”,是一座西洋喷泉,还有万花阵迷宫以及西洋楼等,都具有意大利文艺复兴时期的风格。在...至此,圆明园已经过了火劫、木劫和石劫,建筑、林木、砖石皆已荡然无存,它的悲惨命运是否终结了呢?还...更多关于圆明园的资料的问题>> 查看同主题问题: 圆明园 等待您来回答2回答10兄弟敦和睦,朋友笃诚信 ...
宽度优先搜索与深度优先搜索有何区别
答：详细来说，宽度优先搜索是一种盲目搜索方法，它按层次顺序搜索，先访问离起始顶点最近的顶点。在宽度优先搜索中，所有相邻节点将在当前节点之后访问，这意味着它首先访问树的当前级别的所有节点，然后移至下一级别，因此称为宽度优先。举个例子，我们在解决迷宫问题时，通常会选择宽度优先搜索，从起点开始，...
深度优先和宽度优先有什么区别呢?
答：详细来说，宽度优先搜索是一种盲目搜索方法，它按层次顺序搜索，先访问离起始顶点最近的顶点。在宽度优先搜索中，所有相邻节点将在当前节点之后访问，这意味着它首先访问树的当前级别的所有节点，然后移至下一级别，因此称为宽度优先。举个例子，我们在解决迷宫问题时，通常会选择宽度优先搜索，从起点开始，...
为什么在图中要用宽度优先搜索算法?
答：详细来说，宽度优先搜索是一种盲目搜索方法，它按层次顺序搜索，先访问离起始顶点最近的顶点。在宽度优先搜索中，所有相邻节点将在当前节点之后访问，这意味着它首先访问树的当前级别的所有节点，然后移至下一级别，因此称为宽度优先。举个例子，我们在解决迷宫问题时，通常会选择宽度优先搜索，从起点开始，...
什么是深度优先搜索和宽度优先搜索?
答：详细来说，宽度优先搜索是一种盲目搜索方法，它按层次顺序搜索，先访问离起始顶点最近的顶点。在宽度优先搜索中，所有相邻节点将在当前节点之后访问，这意味着它首先访问树的当前级别的所有节点，然后移至下一级别，因此称为宽度优先。举个例子，我们在解决迷宫问题时，通常会选择宽度优先搜索，从起点开始，...
什么是深度优先搜索和宽度优先搜索?
答：详细来说，宽度优先搜索是一种盲目搜索方法，它按层次顺序搜索，先访问离起始顶点最近的顶点。在宽度优先搜索中，所有相邻节点将在当前节点之后访问，这意味着它首先访问树的当前级别的所有节点，然后移至下一级别，因此称为宽度优先。举个例子，我们在解决迷宫问题时，通常会选择宽度优先搜索，从起点开始，...
什么是宽度优先搜索?
答：详细来说，宽度优先搜索是一种盲目搜索方法，它按层次顺序搜索，先访问离起始顶点最近的顶点。在宽度优先搜索中，所有相邻节点将在当前节点之后访问，这意味着它首先访问树的当前级别的所有节点，然后移至下一级别，因此称为宽度优先。举个例子，我们在解决迷宫问题时，通常会选择宽度优先搜索，从起点开始，...
