迷宫问题 （C语言代码）

解题思路:利用广搜遍历

注意事项:若无路径则为-1

参考代码:

#include<stdio.h>

char c[200][200];//创建迷宫数组

int a,b;//迷宫大小

int q[4][2]={-1,0,0,1,1,0,0,-1};//4个方向移动

void op(int tarx,int tary)

{

int book[200][200];//book用于记录哪些点已遍历过

for(int i=0;i<a;i++)

for(int j=0;j<b;j++)

book[i][j]=0;

struct op//队列

{

int x;//横坐标

int y;//纵坐标

int s;//步数

}que[400];//定义队列

int flat=1,head=1;//head表示正扩展的结点，tail位于队尾最后一个元素的后面随时将head扩展出来的结点入队

que[flat].x=tarx;

que[flat].y=tary;

que[flat].s=0;

book[tarx][tary]=1;

flat++;

int tx,ty;

while(head<flat)

{

for(int i=0;i<4;i++)//枚举4个方向

{

tx=que[head].x+q[i][0];

ty=que[head].y+q[i][1];

if(tx<0||tx>=a||ty<0||ty>=b)//判断是否出界

continue;

if(book[tx][ty]==0&&c[tx][ty]!='#')//判断是否为障碍，是否已经走过

{

book[tx][ty]=1;//记录当前节点已走过，广搜每个节点只搜索一次

que[flat].x=tx;

que[flat].y=ty;

que[flat].s=que[head].s+1;

flat++;//每入队一次tail++

}

if(c[tx][ty]=='E')//是否找到出口

{

printf("%d\n",que[flat-1].s);

return;

}

}

head++;

}

printf("-1\n");//没找到出口输出-1

}

int main()

{

int n;

scanf("%d",&n);

for(int i=0;i<n;i++)

{

int tarx,tary;

scanf("%d%d",&a,&b);

for(int j=0;j<a;j++)

scanf("%s",c[j]);

for(int j=0;j<a;j++)

{

int k=0;

for(int u=0;u<b;u++)

{

if(c[j][u]=='S')//找起点

{

tarx=j;

tary=u;

k=1;

break;

}

}

if(k)

break;

}

op(tarx,tary);//起点，终点

}

}