广度优先搜索（宽度优先搜索）迷宫问题

118 阅读 0 评论 78 点赞

我是靠谱客的博主专注蚂蚁，这篇文章主要介绍广度优先搜索（宽度优先搜索）迷宫问题，现在分享给大家，希望可以做个参考。

使用队列，层层递进，往下扩展。

     5 4
     0 0 1 0
     0 0 0 0
     0 0 1 0
     0 1 0 0
     0 0 0 1
     1 1 4 3

（5,4是迷宫的行和列，0代表空地，1代表障碍物，1,1是起始位置，4,3 是需要到达的位置）
7

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
struct note
{
int x;
int y;
int s;//步数
};
int main()
{
struct note que[2501];
int a[51][51]={0},book[51][51]={0};
int next[4][2]={0,1, 1,0, 0,-1, -1,0};
int head,tail;
int i,j,k,n,m,sx,sy,ex,ey,tx,ty,flag;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
head=1;
tail=1;//队列初始化
que[tail].x=sx;
que[tail].y=sy;
que[tail].s=0;
tail++;
book[sx][sy]=1;
flag=0;
while(head<tail)
{
for(k=0;k<4;k++)
{
tx=que[head].x+next[k][0];
ty=que[head].y+next[k][1];
if(tx<1||tx>n||ty<1||ty>m)
continue;
if(a[tx][ty]==0&&book[tx][ty]==0)
{
book[tx][ty]=1;
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[head].s+1;
tail++;
}
if(tx==ex&&ty==ey)
{
flag=1;
break;
}
}
if(flag==1)
break;
head++;
}
printf("%d",que[tail-1].s);//tail指向队列队尾的下一个位置，所以需要-1.
return 0;
}