算法分析与设计迷宫算法
1. 试设计迷宫求解算法:迷宫是一个m行n列的0-1矩阵,其中0表示无障碍,1表示有障碍
假设8个方位被简单定义为 char a[8];
int path(point *location)
{
if(“location不为出口”&&“location.a[0]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[1]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[2]未涉足过”)
path(location->a[0]);
` ````````````````````
``````````
``````
``
else return 0;
}
这是一个迭代过程，需要对每一个方位的位置都遍历一遍，也是一个深度优先的遍历过程。
我在这只给lz一个示意，具体的算法在《数据结构》的书上基本都有，蛮经典的。希望能对lz有所帮组。
加油！
2. 数据结构 迷宫问题算法
//迷宫求解（自定义一个2维矩阵作为地图）
void Labyrinth()
{
printf("自定义迷宫矩阵：\n");
int a[10][10];
int i,j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
scanf("%d",&a[i][j]);
printf("\n");
coordinate *Laby = new coordinate[100];
int n=1;
int x,y;
Laby[1].x=x=1;
Laby[1].y=y=6;
Laby[1].step=1;
a[1][6]=2;
SqStack S;
InitStack(S);
Push(S,0);
Push(S,1);
i=1;
while(GetTop(S))
{
if(a[x][y]==100)
{
printf("找到终点了!!!\n");
break;
}
i++;
if(n==1)
a[x][y]=i;
if(a[x][y-1]==1||a[x-1][y]==100)
{
Push(S,i);
Laby[i].x=x;
Laby[i].y=y=y-1;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x-1][y]==1||a[x-1][y]==100)
{
Push(S,i);
Laby[i].x=x=x-1;
Laby[i].y=y;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x][y+1]==1||a[x][y+1]==100)
{
Push(S,i);
Laby[i].x=x;
Laby[i].y=y=y+1;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x+1][y]==1||a[x+1][y]==100)
{
Push(S,i);
Laby[i].x=x=x+1;
Laby[i].y=y;
Laby[i].step=i;
n=1;
continue;
}
else
{
Pop(S,i);
x=Laby[i].x;
y=Laby[i].y;
a[x][y]=-1;
n=0;
}
}
if(!GetTop(S))
printf("没有找到出路!\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
printf("%d ",a[i][j]);
printf("\n");
}
}
我没有给出栈的代码，你自己应该有吧！
具体迷宫算法 就是如此 仅供参考
3. 求走迷宫的算法！（计算机的算法）（编程也可以
我的思路：
按照人类走迷宫的方法，贴着左边走，左边有路就向左走，左边没路向前走，左边前面都没路向右走
机器人的应该是：1.判断左边是否有墙，无墙：机器人左转，前进一步，继续判断左。。
2.左边有墙，则判断前方是否有墙，无则向前一步，跳回第一步
3.前方有墙（此时状态是左有墙，前有墙），则向机器人右转，跳回第一步
另外有个前提条件，机器人转弯需要原地转，有转弯半径的肯定不行。
还有个问题，就是机器人自己不知道自己已经从迷宫出来了，会一直走。。
4. 迷宫问题求解的实现算法
源程序：
//base.h
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
//stack.h
#include "base.h"
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct{ //迷宫中r行c列的位置
int r;
int c;
}PostType;
typedef struct{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct{
SElemType* base;//栈基址,构造前销毁后为空
SElemType* top;//栈顶
int stackSize; //栈容量
}Stack; //栈类型
Status InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
free(S.base);
S.top=S.base;
return OK;
5. 迷宫算法的修改编写
#include<stdio.h>
#include<string.h>
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int map[10][10], n=5;
int b[1000],t=0;
bool ok(int x)
{
return x>=1&&x<=n;
}
void DFS(int x,int y)
{
int i,tx,ty;
b[t]=t;
t++;
map[x][y]=0;
for(i=0;i<4;i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(!ok(tx)||!ok(ty)||map[tx][ty]==0)
{
continue;
}
DFS(tx,ty);
}
}
void genMat(){}
int main()
{
int i;
genMat();//这里调用你的算法生成5*5 的矩阵
DFS(1,1);
for(i=0;i<t;i++)printf("%d ",b[i]);
puts("");
return 0;
}
6. 罗密欧与朱丽叶的迷宫问题 算法分析与设计
这里已经有了：
http://apps.hi..com/share/detail/12714033
走完迷宫所有的格子,并且转弯次数最少..
在最后找到朱丽叶.
#include<iostream>
using namespace std;
int dir[9][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int count;
int dirs,best;
int board[20][20],bestw[20][20];
int m,n,k;
int sx,sy,ex,ey;
bool comp(int x,int y)
{
if(x>0&&x<=n&&y>0&&y<=m&&board[x][y]==0)
return true;
else return false;
}
void save()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
bestw[i][j]=board[i][j];
}
void search(int dep,int x,int y,int di)
{
if(dep==m*n-k&&x==ex&&y==ey&&dirs<=best)
{
if(dirs<best)
{
best=dirs;
count=1;
save();
}
else count++;
return;
}
if(dep==m*n-k||x==ex&&y==ey||dirs>best) return;
else
{
for(int i=1;i<=8;i++)
if(comp(x+dir[i][0],y+dir[i][1]))
{
board[x+dir[i][0]][y+dir[i][1]]=dep+1;
if(di!=i) dirs++;
search(dep+1,x+dir[i][0],y+dir[i][1],i);
if(di!=i) dirs--;
board[x+dir[i][0]][y+dir[i][1]]=0;
}
}
}
int main()
{
cin>>n>>m>>k;
int i,j;
int c,d;
memset(board,0,sizeof(board));
for(i=0;i<k;i++)
{
cin>>c>>d;
board[c][d]=-1;
}
cin>>sx>>sy;
cin>>ex>>ey;
board[sx][sy]=1;
best=m*n;
dirs=-1;
/***********************
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
cout<<board[i][j]<<" ";
cout<<endl;
}
***********************/
search(1,sx,sy,0);
cout<<best<<endl;
cout<<count<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<bestw[i][j]<<" ";
cout<<endl;
}
}
来自: http://hi..com/dearshawn/blog/item/a4a32eeb2e8277d9d539c90b.html
7. 迷宫问题算法设计！！急急急（c语言）
额，又是课程设计。。。
迷宫类算法，用栈，队列来做。不过一般来队列，因为队列能够在较短时间内求出最短路径。
在网上搜下，很多的。。
你的要求很难达到。。。
8. 迷宫算法问题
栈走到底也可以回过头来继续探索啊，要不怎么叫深度【遍历】。
9. 迷宫算法
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
int x;
int y;
};
struct Element //"恋"栈元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //链栈
{
Element elem;
struct LStack *next;
}*PLStack;
/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}