导航:首页 > 源码编译 > c语言迷宫算法入门

c语言迷宫算法入门

发布时间:2024-10-26 20:11:32

⑴ C语言迷宫问题,求该算法的时间和空间的复杂度。迷宫的路径已经定义好,求出路的算法。

该算法是不稳定的,其时空复杂度不仅和m,n有关,还和mg[][]的具体数值有关。
最坏情况下:每个点都试探过才走到终点。此时时间复杂度为:(m*n-1)*4,(其中4为4个方向),空间复杂度m*n*2,(其中m*n为存储迷宫图空间,m*n为栈空间);
再好情况下:一次试探过就走到终点。此时时间复杂度为:(min(m,n)-1),空间复杂度m*n;

所以:
该算法时间复杂度为:[(m*n-1)*4+(min(m,n)-1)]/2,约为2×m×n
空间复杂度为3*m*n/2

⑵ 如何用C语言实现求迷宫的最短路径

#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定义迷宫,0表示能走的块,1表示不能走,在外围加上一圈不能走的块
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //块的位置
int pre; //本路径中上一块在队列中的下标
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四个方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循环
}
}
}
return 0;
}

void print(int n) //输出 路径算法
{
int k=n,j,m=1;
printf("\n");
do //将输出的路径上的所有pre改为-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宫最短路径如下:\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}

⑶ c语言菜鸟——迷宫问题。说明——使用DEV-C++编译器。望高手不吝赐教!感激。

typedef struct node
{
int i,j;//横纵坐标
int di;//direction
}st[max];
结构体定义语法错误,typedef是将结构体重命名为另一个名字的,改为:
typedef struct
{
int i,j;//横纵坐标
int di;//direction
}node;
node st[max];
或者:
struct node
{
int i,j;//横纵坐标
int di;//direction
}st[max];

⑷ C语言简单迷宫

for (i=0;i<24;i++)
{
for (j=0;j<25;j++)
printf("%c",a[i][j]);

你的二维数组只有7行8列,可你输出了24行25列,非法访问了内存

改成这样看看

for (i=0;i<7;i++)
{
for (j=0;j<8;j++)
printf("%c",a[i][j]);

阅读全文

与c语言迷宫算法入门相关的资料

热点内容
如何截获手机app连接的ip 浏览:330
冰箱压缩机是否需要电容 浏览:344
python列表每一行数据求和 浏览:274
自己有一台服务器可以玩什么 浏览:656
社会学波普诺pdf 浏览:584
解压做食物的小视频 浏览:758
pdf怎么单独设置文件夹 浏览:474
业务逻辑程序员 浏览:659
addto新建文件夹什么意思 浏览:160
有服务器地址怎么安装软件 浏览:659
安卓如何完全清除数据 浏览:690
安卓安卓证书怎么信任 浏览:53
服务器被攻击如何解决 浏览:221
学霸变成程序员 浏览:881
c语言编译错误fatalerror 浏览:441
ipv4内部服务器地址怎么分配 浏览:463
java线程安全的方法 浏览:952
重复命令画梯形 浏览:164
在疫情就是命令 浏览:329
自己搭建一个什么服务器好玩 浏览:254