输出迷宫的最短路径
本帖最后由 谢坡坡 于 2017-10-16 09:48 编辑#include<stdio.h>
#define M 8 //行数
#define N 8 //列数
#define MaxSize 100 //栈最多元素个数
int mg={ //一个迷宫，其四周要加上均为1的外框
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,1,1,0,1,1,0,1},
{1,0,0,1,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,0,0,1,0,0,1,0,0,1},
{1,0,0,1,1,0,1,0,0,1},
{1,0,1,0,0,0,0,1,0,1},
{1,0,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct migong{
int i; //路径横坐标
int j; //路径纵坐标
int di; //方向
}Stack,Path; //定义栈和存放最短路径的数组
int top=-1; //栈顶指针
int count=1; //路径数计数
int minlen=MaxSize; //最短路径长度
void mgpath()
{ //路径为:(1,1)->(M,N)
int i,j,di,find,k;
top++;
Stack.i=1;
Stack.j=1;
Stack.di=-1;//第一个点入栈
mg=-1; //初始结点进栈
while(top>-1)
{ //栈不空时循环
i=Stack.i;j=Stack.j;di=Stack.di;
if(i==M && j==N)
{ //找到了出口，输出路径
printf("M:",count++);
for(k=0;k<=top;k++)
{
printf("(%d,%d)",Stack.i,Stack.j);
if((k+1)%5==0) //输出时每5个结点换一行
printf("\n\t");
}
printf("\n");
if(top+1<minlen)
{ //比较输出最短路径
for(k=0;k<=top;k++)
Path=Stack;
minlen=top+1;
}
mg.i].j]=0; //让该位置变为其他路径的可走结点
top--;
i=Stack.i;j=Stack.j;di=Stack.di;
}
find=0;
while(di<4 && find==0)
{ //找下一个可走结点
di++;
switch(di)
{
case 0:i=Stack.i-1;j=Stack.j;break; //上面
case 1:i=Stack.i;j=Stack.j+1;break; //右边
case 2:i=Stack.i+1;j=Stack.j;break; //下面
case 3:i=Stack.i;j=Stack.j-1;break; //左边
}
if(mg==0)
find=1;
}
if(find == 1)
{ //找到了下一个可走结点
Stack.di=di; //修改原栈顶元素的di值
top++; //下一个可走结点进栈
Stack.i=i;
Stack.j=j;
Stack.di=-1;
mg=-1; //避免重复走到该结点
}
else
{
mg.i].j]=0; //让该位置变为其他路径的可走结点
top--;
}
}
printf("最短路径如下:\n");
printf("长度:%d\n",minlen);
printf("路径:");
for(k=0;k<minlen;k++)
{
printf("(%d,%d)",Path.i,Path.j);
if((k+1)%5==0) //输出时每5个结点换一行
printf("\n\t");
}
printf("\n");
}
int main(){
printf("迷宫所有路径如下:\n");
mgpath();
return 0;
} 楼主厉害了，学习一下
页:
[1]