c語言迷宮演算法入門

⑴ 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]);