迷宫问题求最小步数
#include<stdio.h>
#include<string.h>
typedef struct node
{
int x;
int y;
int step;
}Node;
int main()
{
int i,j,i1,j1,m=5,n=4,head=0,tail=0;
char map[m][n];
int flag[m][n],next[4][2]={0,1,1,0,0,-1,-1,0};
Node s[m*n];
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
memset(s,0,sizeof(s));
for (i=0;i<m;i++)
gets(map[i]);
for (i=0;i<m;i++)
{
for (j=0;j<n;j++)
{
if (map[i][j]=='S')
{
flag[i][j]=1;
s[tail].x=i;
s[tail].y=j;
s[tail].step=0;
tail++;
}
}
}
while (head<tail)
{
for (i=0;i<4;i++)
{
i1=s[head].x+next[i][0];
j1=s[head].y+next[i][1];
if (i1<0||i1>=m||j1<0||j1>=n)
continue;
if (flag[i1][j1]==0&&(map[i1][j1]=='0'||map[i1][j1]=='E'))
{
flag[i1][j1]=1;
s[tail].x=i1;
s[tail].y=j1;
s[tail].step=s[head].step+1;
tail++;
}
if (map[i1][j1]=='E')
{
printf("该地图至少走%d步可以到达终点",s[tail-1].step);
return 0;
}
}
head++;
}
printf("此地图无解");
}