数据结构:用什么算法可以走出迷宫?
发布网友
发布时间：2022-04-27 00:32
共3个回答
热心网友
时间：2022-06-21 18:28
算法应该很多的，循环的，递归的，还有用栈的我有两个可以看看，第一个是网络上下的，后面的是我自己编的和修改的
1.
//////////////////////////////////////////////////////////////////////
//文件名 :Maze.cpp
//功能 : 线性表的应用——迷宫求解
//创建 : 2007.6.20
//修改日期 : 2007.6.20
//作者 :
////////////////////////////////////////////////////////////////////////
#include <windows.h>
#include <iostream>
#include <stdio.h>
#include<time.h>
//#include "format.h"
//#include "stack.h"
using namespace std;
#define OK 0
#define ERR -1
#define UP '↑' //用于存储方向的常量
#define DOWN '↓'
#define LEFT '→'
#define RIGHT '←'
#define Rank 20
#define File 63
#define Rand 16
char Maze[Rank][File]; //定义存储迷宫用的字符型二维数组
char mark=1; //标记
char Bar=2; //地图
char Player=12; //游戏者
typedef struct SNode
{
int data;
struct SNode *next;
}SNode;
typedef struct
{
int length;
SNode *top;
}STACK;
void InitStack(STACK *S)
{
S->top=NULL;
S->length=0;
}
/*元素e入栈*/
int Push(STACK *S,int e)
{
SNode *p;
p=new SNode[sizeof(SNode)];
if(!p) return ERR;
p->data=e;
p->next=S->top;
S->top=p;
S->length++;
return OK;
}
/*栈顶元素出栈,e带回栈顶元数*/
int Pop(STACK *S,int *e)
{
SNode *p;
if(S->top==NULL) return ERR;
p=S->top;
*e=p->data;
S->top=p->next;
S->length--;
delete p;
return OK;
}
/*判断S是否为空栈*/
int Empty(STACK S)
{
if(S.top==NULL) return OK;
return ERR;
}
void ShowMaze();
void InitMaze();
void RunMaze();
int main()
{
int i=1;
system("color 1E");
while(i==1)
{
RunMaze();
cout<<"\t\t 『选择：Prsss 1：再来一次 Else：退出程序』\n";
cin>>i;
}
return 0;
}
void ShowMaze()
{
int i,j;
system("cls");
cout<<"\n\t\t\t 『迷 宫 求 解』"<<"\n";
cout<<"\t\t 『注:"<<Player<<"为游戏者"<<Bar<<"为地图障碍"<<mark<<"为所留印记』"<<endl;
for(i=0;i<Rank;i++)
{
cout<<"\t"<<Bar;
for(j=0;j<File;j++)
cout<<Maze[i][j];
cout<<Bar<<"\n";
}
}
void InitMaze()
{
int i,j;
for(i=0;i<Rank;i++)
for(j=0;j<File;j++)
Maze[i][j]=Bar;
srand((unsigned)time(NULL));
int n;
cout<<"请输入数字选图";
cin>>n;
for(i=1;i<Rank-1;i++) //for开始
for(j=1;j<File;j++)
{
//n=rand()%Rand; //随机函数
//if(n<Rand*2/3) Maze[i][j]=' ';
if (((n^i+4*j^3))%11!=5)Maze[i][j]=' ';
} //for结束
Maze[1][0]=' '; //给迷宫留入口
Maze[1][1]=' ';
Maze[1][2]=' ';
Maze[1][3]=' ';
Maze[Rank-2][File-4]=' '; //给迷宫留出口
Maze[Rank-2][File-3]=' ';
Maze[Rank-2][File-2]=' ';
Maze[Rank-2][File-1]=' ';
}
void RunMaze()
{
int path,i=1,j=0,speed=0;
time_t Start,End;
STACK S; //定义一个用于存储走过的路线的栈
time(&Start);
InitMaze(); //随机成生迷宫
InitStack(&S); //初始化栈
Maze[1][0]=Player; //初始化位置
ShowMaze(); //显示迷宫
cout<<"\n\t\t\t『请选择速度:1 快速 2 较慢 』"<<endl;
while(speed!=1 && speed!=2) cin>>speed;
while(i>=0 && i<Rank && j>=0 && j<File)//开始遍历迷宫
{
ShowMaze(); //显示迷宫
if(speed==2) //选择2较慢时进入空循环延时
Sleep(100);
if(i==Rank-2&&j==File-1) //判断是否到达出口
{
time(&End);
cout<<"\n\t\t『恭喜成功走出!所用的步数为:"<<S.length<<" 所用时间："<<End-Start<<" 秒』"<<endl;
return;
}
if(Maze[i][j+1]==' ') //向右走一步
{
char dir=26;
Maze[i][j]=dir;
j=j+1;
Maze[i][j]=Player;
Push(&S,RIGHT);
}
else
{
if(Maze[i+1][j]==' ') //向下走一步
{
char dir=25;
Maze[i][j]=dir;
i=i+1;
Maze[i][j]=Player;
Push(&S,DOWN);
}
else
{
if(Maze[i-1][j]==' ') //向上走一步
{
char dir=24;
Maze[i][j]=dir;
i=i-1;
Maze[i][j]=Player;
Push(&S,UP);
}
else
{
if(Maze[i][j-1]==' ') //向左走一步
{
char dir=27;
Maze[i][j]=dir;
j=j-1;
Maze[i][j]=Player;
Push(&S,LEFT);
}
else //遇到障碍往回走一步
{
if(Empty(S)==OK) //判断是否回到起点了,是则退出程序
{
time(&End);
cout<<"\n\t\t\t『迷宫没有出路! 所用时间："<<End-Start<<"秒』\n";
return;
}
else
{
if(Pop(&S,&path)==OK) //判断能否取回上一步路径
{
switch(path)
{
case LEFT:
Maze[i][j]=mark;
j=j+1;
Maze[i][j]=Player;
break;
case UP:
Maze[i][j]=mark;
i=i+1;
Maze[i][j]=Player;
break;
case DOWN:
Maze[i][j]=mark;
i=i-1;
Maze[i][j]=Player;
break;
case RIGHT:
Maze[i][j]=mark;
j=j-1;
Maze[i][j]=Player;
break;
} //结束分支语句switch
} //结束判断能否取回上一步路径
}
}
}
}
}
} //结束while循环
}
第二个。
#include <windows.h>
#include <iostream>
#include <stdio.h>
#include<time.h>
//#include "format.h"
//#include "stack.h"
using namespace std;
//#define OK 0
//#define ERR -1
//#define UP '↑' //用于存储方向的常量
//#define DOWN '↓'
//#define LEFT '→'
//#define RIGHT '←'
#define Rank 17
#define File 63
#define Rand 16
char Maze[Rank][File]; //定义存储迷宫用的字符型二维数组
char mark=1; //标记
char Bar=2; //地图
char Player=12; //游戏者
void ShowMaze();
void InitMaze();
void RunMaze();
int main()
{
int i=1;
system("color 1E");
while(i==1)
{
RunMaze();
cout<<"\t\t 『选择：Prsss 1：再来一次 Else：退出程序』\n";
cin>>i;
}
return 0;
}
void ShowMaze()
{
int i,j;
system("cls");
cout<<"\n\t\t\t 『迷 宫 求 解』"<<"\n";
cout<<"\t\t 『注:"<<Player<<"为游戏者"<<Bar<<"为地图障碍"<<mark<<"为所留印记』"<<endl;
for(i=0;i<Rank;i++)
{
cout<<"\t"<<Bar;
for(j=0;j<File;j++)
cout<<Maze[i][j];
cout<<Bar<<"\n";
}
}
void InitMaze()
{
int i,j;
for(i=0;i<Rank;i++)
for(j=0;j<File;j++)
Maze[i][j]=Bar;
srand((unsigned)time(NULL));
int n=5;
cout<<"请输入数字选图";
cin>>n;
for(i=1;i<Rank-1;i++) //for开始
for(j=1;j<File;j++)
{
//n=rand()%Rand; //随机函数
//if(n<Rand*2/3) Maze[i][j]=' ';
if (((n^i+4*j^3))%5!=1)Maze[i][j]=' ';
} //for结束
Maze[1][0]=' '; //给迷宫留入口
Maze[1][1]=' ';
Maze[1][2]=' ';
Maze[1][3]=' ';
Maze[Rank-2][File-4]=' '; //给迷宫留出口
Maze[Rank-2][File-3]=' ';
Maze[Rank-2][File-2]=' ';
Maze[Rank-2][File-1]=' ';
}
void RunMaze()
{ int a=2;
int i=1,j=1,speed=0;
time_t Start,End;
//STACK S; //定义一个用于存储走过的路线的栈
time(&Start);
InitMaze(); //随机成生迷宫
//InitStack(&S); //初始化栈
//Maze[1][0]=Player; //初始化位置
ShowMaze(); //显示迷宫
cout<<"\n\t\t\t『请选择速度:1 快速 2 较慢 』"<<endl;
while(speed!=1 && speed!=2) cin>>speed;
while(i>=0 && i<Rank && j>=0 && j<File)//开始遍历迷宫
{
ShowMaze(); //显示迷宫
if(speed==2) //选择2较慢时进入空循环延时
Sleep(100);
if(i==Rank-2&&j==File-1) //判断是否到达出口
{
time(&End);
cout<<"\n\t\t『恭喜成功走出!"<<" 所用时间："<<End-Start<<" 秒』"<<endl;
return ;
}
else
{
switch(a)
{
case 1:if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j+1]==' '||Maze[i][j+1]==26)
{j=j+1;
a=1;
Maze[i][j]=26;
break;
}else
if (Maze[i+1][j]==' '||Maze[i+1][j]==26)
//if(Maze[i+1]][j]==' '||Maze[i+1][j]==26)
{i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
case 2:if(Maze[i][j+1]==' '||Maze[i][j+1]==26)
{
j=j+1;
a=1;
Maze[i][j]=26;
break;
}
else
if(Maze[i+1][j]==' '||Maze[i+1][j]==26)
{
i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
if(Maze[i][j-1]==' '||Maze[i][j-1]==26)
{
j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
case -1:if (Maze[i+1][j]==' '||Maze[i+1][j]==26)
{i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j-1]==' '||Maze[i][j-1]==26)
{j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
{
a=-a;
Maze[i][j]=26;
break;
}
case -2:if (Maze[i][j-1]==' '||Maze[i][j-1]==26)
{j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j+1]==' '||Maze[i][j+1]==26)
{j=j+1;
a=1;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
}
if (i==1&&j==1)
{
time(&End);
cout<<"迷宫没有出路"<<"所用时间"<<End-Start<<endl;
return;
}
}
} //结束while循环
}
热心网友
时间：2022-06-21 18:28
小窍门：闭上眼，靠着一边墙一直走，可以走出迷宫。
热心网友
时间：2022-06-21 18:29
用高度吧，再加上一双眼睛就行
