迷宫问题全部路径和最短路径求解,C\C++交流,技术交流,鱼C论坛

程序员的救赎 发表于 2019-5-26 17:51:26

迷宫问题全部路径和最短路径求解

下面的代码能找出一条路径，不知道怎么修改才能求出全部路径。

以下是输入的迷宫：
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 0 1 0 0 0 0 0 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 0 1 1 0 0 0 1
1 0 1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1

#include <iostream>
#include<stack>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
const int XLEN=8,YLEN=10;//默认迷宫行数和列数
int m,p;// 出口坐标
int maze;//迷宫数组
int mark;//访问标记数组
struct Offsets{
int a,b;//a和b是x y方向的偏移
};
Offsets directions={
{-1,0},//上
{-1,1},//右上
{0,1},//右
{1,1},//右下
{1,0},//下
{1,-1},//左下
{0,-1},//左
{-1,-1},//左上
};
struct items{
int x,y,dir;//栈结点定义
};

void outputpath(stack<items> a, items Tmp) {
stack<items> b;
b.push(Tmp);
while(!a.empty()){
b.push(a.top());
a.pop();
}
while(!b.empty()){
cout<<"<"<<b.top().x<<","<<b.top().y<<">"<<" ";
b.pop();

}
}
void Path(int x,int y,int m,int n){//x,y为入口坐标，m,n为出口坐标
int i,j,g,h,d = 0; // i，j为当前位置， g,h为下一步的位置，d为下一步的方向
stack<items> S;//设置工作栈
stack<items> St;//输出栈
items tmp;
items Tmp;
mark=1;//x,y是入口
tmp.x=x,tmp.y=y;
tmp.dir=0;
S.push(tmp);//入口坐标入栈
while(!S.empty()){//当栈不空，一直走下去
tmp=S.top();//取栈顶元素
S.pop();
i=tmp.x;
j=tmp.y;//取当前位置的坐标
d=tmp.dir;
while(d<8){
//找下一位置(g,h)
g=i+directions.a;
h=j+directions.b;
if(g==m && h==n){//到达出口
//逆向存入输出栈
Tmp.x=m,Tmp.y=n;
outputpath(S, Tmp);
mark=1;//标记已被访问
return;
}

//未到达出口
if(maze==0 && mark==0){//如果可通且未被访问
mark=1;//标记已被访问
tmp.x=i;
tmp.y=j;
tmp.dir=d;//记录已走过的位置和前进的方向
S.push(tmp);
i=g;
j=h;
d=0;}//移到(g,h)在各个方向试探
else//试探下一个方向
d++;
}
}
}
int main(int argc, char** argv) {
int i,j,x,y,m,n;
cout<<"迷宫如下图所示："<<endl;
for(i=0;i<XLEN;i++){
for(j=0;j<YLEN;j++){
   cin>>maze;
   mark=0;
}
}

cout<<"迷宫所有路径如下："<<endl;
Path(1,1,XLEN-2,YLEN-2);
// cout<<"最短路径如下："<<endl;
// cout<<"长度为："<<
// cout<<"通路为："<<
return 0;
}

程序员的救赎 发表于 2019-5-26 17:58:47

主要是最近在用Python，大一的数据结构都忘得差不多了。

迷雾少年 发表于 2019-5-28 00:07:28

dfs可以很简单实现

迷雾少年 发表于 2019-5-28 00:24:38

#include <iostream>
using namespace std;
//0 为可以移动 1为障碍
int map[] =
{
1,1,1,1,1,1,1,1,1,1,
1,0,1,1,1,0,1,1,1,1,
1,0,0,0,0,1,1,1,1,1,
1,0,1,0,0,0,0,0,1,1,
1,1,1,1,1,0,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,1,1,0,0,1,1,0,1,
1,0,0,0,0,0,0,0,0,1 };
struct point
{
int x, y;
};
point steps = { 0 };
int startx = 1, starty = 1;
int endx = 5, endy = 3;
int direct[] = { {-1,0},{1,0},{0,-1},{0,1} };
int row = 8, col = 10;//8行10列地图

void dfs(int deep, int x, int y)
{
int i;
if (x<0 || x>row - 1 || y<0 || y>col - 1 || map == 1)
return;
point tmp = { x,y };
steps = tmp;
if (x == endx && y == endy) {//终点
for (i = 0; i < deep+1; i++) {
printf("(%d,%d)-", steps.x, steps.y);
}
printf("\n");
return;
}
for (i = 0; i < 4; i++)
{
map = 1;
dfs(deep + 1, x + direct,y+direct);
map = 0;
}
}

int main()
{
point t = { startx,starty };
dfs(0, startx, starty);
return 0;
}

(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-

程序员的救赎 发表于 2019-5-28 09:41:38

迷雾少年发表于 2019-5-28 00:24
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1 ...

···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下{:10_277:}

迷雾少年 发表于 2019-5-28 16:10:58

程序员的救赎发表于 2019-5-28 09:41
···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

八个方向x-1,y-1,x+1,y+1,x-1,y+1,x-1,y+1就可以了

迷雾少年 发表于 2019-5-28 16:12:06

程序员的救赎发表于 2019-5-28 09:41
···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

dfs递归用的就是栈啊，原理一样

页: [1]

鱼C论坛's Archiver

迷宫问题全部路径和最短路径求解