BFS学习
BFS，广度优先搜索，也称深度优先搜索，即搜索每次可达的所有点并进行标记，直到搜索范围覆盖所需要寻找的点。下面我们从迷宫搜索来看看DFS的应用。

迷宫搜索

寻找迷宫中从起点到终点的最短可行路径。

解题思路

用二维数组记录迷宫，并标记迷宫的障碍点，再通过DFS找出最短路径。

代码

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
#include <cstdio>
struct note{
    int x;
    int y;
    int f;
    int s;
};
int next[4][2]={
    {0,1},{1,0},{0,-1},{-1,0}
};
int main()
{
    struct note que[2501];
    int a[51][51]={0},book[51][51]={0};
    int m,n;scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        scanf("%d",&a[i][j]); 
    int startX,startY,endX,endY,tx,ty;
    scanf("%d%d%d%d",&startX,&startY,&endX,&endY);
    book[startX][startY]=1;
    int flag=0;
    int head=1,tail=2;
    que[head].x=startX;que[head].y=startY;
    que[head].f=0;que[head].s=0;
    while(head<tail)
    {
        for(int i=0;i<4;i++){
            tx=que[head].x+next[i][0];
            ty=que[head].y+next[i][1];
            if(tx<1||tx>m||ty<1||ty>n)
                continue;
            if(a[tx][ty]==0&&book[tx][ty]==0){
                book[tx][ty]=1;
                que[tail].x=tx;
                que[tail].y=ty;
                que[tail].f=head;
                que[tail].s=que[head].s+1;
                tail++;
            }
            if(que[tail].x==endX&&que[tail].y==endY){
                flag=1;
                break;
            }
        }
        if(flag==1) break;
        head++;
    }
    printf("%d\n",que[tail-1].s);
}