深搜dfs和广搜bfs（例题）_深搜和广搜典型例题

题目：（dfs or bfs）

input：第一行具有两个正整数n，m，用空格隔开（1≤ n，m ≤100），n用于行，m为列。
接着有两个正整数X，Y，用空格隔开（1≤ X ≤ n，1≤ Y ≤ m）指示终点坐标。
接下来是n行和m列的映射，0表示空白区域，1表示障碍物，起点坐标固定（1，1）。
（只能上，下，左或右，每步需要1分钟。输入数据确保终点可以到达）
output：输出从起点到终点所需的最短时间（单位：分钟）
Sample Input
5 4
4 3
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
Sample Output
7

使用广度优先搜索（bfs）：

/*AC 1MS，使用内存628K*/
#include<stdio.h>
struct note
{
    int x;
    int y;
    int time;
};
int main()
{
    struct note queue[10005];
    int a[102][102]={0},book[102][102]={0};
    int c[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    int head,tail,n,m,f,d,i,j,z,tx,ty;
    scanf("%d %d %d %d",&n,&m,&f,&d);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    head=1,tail=1;
    queue[tail].x=1,queue[tail].y=1,queue[tail].time=0;
    tail++;
    book[1][1]=1;
    z=0;
    while(head<tail)
    {
        for(int k=0;k<4;k++){
            tx=queue[head].x+c[k][0];
            ty=queue[head].y+c[k][1];
            if(tx>n||tx<1||ty>m||ty<1)
                continue;
            if(a[tx][ty]==0&&book[tx][ty]==0){
                book[tx][ty]=1;
                queue[tail].x=tx;
                queue[tail].y=ty;
                queue[tail].time=queue[head].time+1;
                tail++;
            }
            if(tx==f&&ty==d){
                z=1;
                break;
            }
        }
        if(z)
            break;
        head++;
    }
    printf("%d\n",queue[tail-1].time);
    return 0;
}
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

下面为标程代码：

// 结果：Accepted 运行时间：4ms 使用内存：768KB
#include<iostream>
#include<queue>
using namespace std;
const int maxn=110;
int mp[maxn][maxn],aimx,aimy,n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};

struct node {
    int x,y,s;
    node(int _x=0,int _y=0,int _s=0){
        x=_x;y=_y;s=_s;
    }
}beg, in, out;

int bfs( ) {
    queue<node>Q; 
    Q.push(node(1,1,0));
    while( !Q.empty() ) {
        out = Q.front(); Q.pop();
        for( int i=0; i<4; i++ ) {
            in.x=out.x+dir[i][0];
            in.y=out.y+dir[i][1];
            in.s=out.s+1;
            if(in.x<1||in.x>n||in.y<1||in.y>m)
            	continue;
            if(mp[in.x][in.y])
            	continue;
            mp[in.x][in.y]=1;
            if(in.x==aimx&&in.y==aimy)
            	return in.s;
            Q.push(in);
        }
    }
    return -1;
}

int main(){
    cin>>n>>m>>aimx>>aimy;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    cout<<bfs()<<endl;
    return 0;
}

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

使用深度优先搜索（dfs）：

/*该代码超时*/
#include<stdio.h>
#define inf 0x3f3f3f3f
int n,m,x,y,a[102][102],book[102][102],min=inf,time=0;
void dfs(int i,int j,int time)
{
    int tx,ty,q;
    int b[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    if(i==x&&j==y){
        if(time<min)
            min=time;
        return;
    }
    for(int q=0;q<4;q++){
        tx=i+b[q][0];
        ty=j+b[q][1];
        if(tx>n||tx<1||ty>m||ty<1)
            continue;
        if(a[tx][ty]==0&&book[tx][ty]==0){
            book[tx][ty]=1;
            dfs(tx,ty,time+1);
            book[tx][ty]=0;
        }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d",&x,&y);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    book[1][1]=1;
    dfs(1,1,time);
    printf("%d\n",min);
    return 0;
}

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

题目：走迷宫（dfs）

有多个测试用例。
每个测试用例的第一行是2个整数 m, n ，表示迷宫的长度和宽度。0 < m, n ≤ 50
第二行是4个整数 a, b, c, d，其中(a, b)表示迷宫的入口坐标，(c, d)表示出口坐标。
最后一个用例，m=n=0，不用处理。
Output
对每个迷宫输出一行结果，如果该迷宫有解，则输出"YES"，否则输出"NO"。
Sample Input
5 5
0 0 4 4
.#…#
.#…#
…#
#.#…
#…
0 0
Sample Output
YES

深搜代码如下（dfs）：

#include<stdio.h>
#include<string.h>
int m,n,c,d,z;
char a[51][51],book[51][51];
void dfs(int i,int j)
{
    int x,y;
    char next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    if(i==c&&j==d){
        z=1;
        return;
    }
    for(int k=0;k<4;k++){
        x=i+next[k][0];
        y=j+next[k][1];
        if(x>m-1||x<0||y>n-1||y<0)
            continue;
        if(a[x][y]=='.'&&book[x][y]==0){
            book[x][y]=1;
            dfs(x,y);
        if(z)
            return;
            ///book[x][y]=0;///多这一句会超时，why？
        }
    }
    return;
}
int main()
{
    int first_x,first_y;
    while(~scanf("%d%d",&m,&n))
    {
        memset(book,0,sizeof(book));
        z=0;
        if(!m&&!n)
            break;
        scanf("%d %d %d %d",&first_x,&first_y,&c,&d);

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                scanf(" %c",&a[i][j]);
            }
        }
        book[first_x][first_y]=1;
        dfs(first_x,first_y);
        if(!z||a[first_x][first_y]=='#')
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

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

题目：捕牛计（Catch That Cow）（bfs）

http://poj.org/problem?id=3278
Description
农民John刚刚获悉一头逃跑的牛的位置，打算立刻就去把它抓回来。John和牛都站在一条直线上，开始时John位于坐标点N上（ 0 ≤ N ≤ 100,000 ），牛位于坐标点K上（ 0 ≤ K ≤ 100,000 ）。John有两种行动方式：步行和瞬移（这种技能不是一般群众具备的）。

步行：John花一分钟由任意点X移动到点X-1或点X+1。

瞬移：John花一分钟由任意点X移动到点2*X。

假设牛不知道John来抓它，一直站在原地吃草。问John最少需要花多少分钟才能抓到它？

Input
有多个测试用例，每个用例一行，有两个整数：N和K，用空格分隔。最后一行是两个 -1，不用处理。

Output
为每个用例输出一行一个整数：John抓住逃跑的牛最少需要多少分钟。

Sample Input
5 17
-1 -1

Sample Output
4

广搜代码如下（bfs）：

#include<bits/stdc++.h>
using namespace std;
int N,K;
struct node
{
    int x,time;
};
int main()
{
    while(cin>>N>>K) 
    {
        if(N==-1&&K==-1)break;
        if(N>=K){	///特判，当N=K时结果是为0，如果N=K时去广搜会得到2的结果
            cout<<N-K<<endl;
            continue;
        }
        struct node queue[100005];
        int head=1,tail=1,tx,ty,z=0,book[100005]={};
        queue[tail].x=N,queue[tail].time=0;
        tail++;
        while(head<tail)  ///队列为空时说明所有的都搜索完了 
        {
            for(int i=1;i<=3;i++){
                switch(i){  ///三种情况
                    case 1:tx=queue[head].x+1;break;
                    case 2:tx=queue[head].x-1;break;
                    case 3:tx=2*queue[head].x;break;
                }
                if(tx<0||tx>100001)continue;///排除出界情况
                if(book[tx]==0)
                    book[tx]=1,
                    queue[tail].x=tx,
                    queue[tail].time=queue[head].time+1,
                    tail++;
                if(tx==K){
                    z=1;
                    break;
                }
            }
            if(z)
                break;
            head++;
        }
        cout<<queue[tail-1].time<<endl;
    }
    return 0;
}

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

题目：是否可达（bfs）

Description
给出一个有向图，请判断图中某顶点a是否可到达另一顶点b 。

Input
多测试用例。每个测试用例如下：

第一行给出该有向图的顶点数 n （ 1 ≤ n ≤ 1000 ）。 顶点从1开始编号。

第二行给出该有向图的边数 e （ 0 ≤ e ≤ 200000 ）。

第三行开始，共e行，每行两个正整数 a b，表示从顶点a发出一条弧到顶点b。

接下来是一个正整数T，表示有T个提问。

接下来T行，每行两个整数u v，表示提问从顶点u是否可到达顶点v。

Output
为每个测试用例输出T行，对应每个提问，如果从顶点u可以到达顶点v，输出一行yes，否则输出no。

然后输出一个空行。

Sample Input
4
6
1 2
1 3
2 3
2 1
3 2
2 4
5
1 2
3 1
1 4
4 1
4 4

Sample Output
yes
yes
yes
no
yes

广搜代码如下（bfs）：

#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int qq[1003][1003];
int que[100003];
int main()
{
    int n,e,T;
    while(~scanf("%d%d",&n,&e))
    {
        int a,b,u,v;
        memset(qq,0,sizeof(qq));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i==j)qq[i][j]=0;
                else qq[i][j]=inf;
        for(int i=1;i<=e;i++){
            scanf("%d%d",&a,&b);
            qq[a][b]=1;
        }
        scanf("%d",&T);
        while(T--)
        {
            memset(que,0,sizeof(que));
            int y=0;
            int book[1003]={},ww;
            scanf("%d%d",&u,&v);
            if(u==v){  ///当u==v时需要特判，因为book[u]=1标记之后，book[v]也同样被标记了，导致无法从u点拓展到v点
                printf("yes\n");
                continue;
            }
            int head=1,tail=1;
            que[tail++]=u;
            book[u]=1;
            while(head<tail&&tail<=n)
            {
                ww=que[head];
                for(int i=1;i<=n;i++){
                    if(qq[ww][i]==1&&book[i]==0){
                        que[tail]=i;
                        if(que[tail]==v){
                            y=1;break;
                        }
                        tail++;
                        book[i]=1;
                    }
                    if(tail>n)break;
                }
                if(y)break;
                head++;
            }
            if(!y)
                printf("no\n");
            else
                printf("yes\n");
        }
        puts("");
    }
    return 0;
}

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
57
58
59
60
61
62

题目：逃出暗黑地牢（bfs）

Time Limit: 1000/500 MS (Java/Others)
Description
你被困在一个三维地牢中了，哈哈哈哈，逃吧，赶快寻找一条最快的路逃命吧，洪水就快要淹没地牢了。地牢可以看作由若干正方块组成，有些方块是石头，有些则是空置的，人可走动。从一个方块向北、向南、向东、向西、向上、向下走到另一个位置，需要一分钟。不可以斜向走动，迷宫四周被石头包围着。
你是否可以逃出来？如果可以，需要多少时间？

Input
测试数据有多个地牢。描述每个地牢的第一行是3个整数 L、R和C （均不超过30）。

L表示地牢的层数。
R和C表示每层地牢的行和列数。

接下来是L个矩阵（每个矩阵表示一层），每个矩阵R行，每行C个字符。每个字符表示地牢的一个方块。石头方块用 ‘#’ 表示，空的方块用 ‘.’ 表示。你的起始位置用’S’表示，地牢出口用’E’表示。 每一层之间用一个空行分隔。
当L = R = C = 0 时，表示输入结束。

Output
每个迷宫地牢输出一行结果。如果可以走到出口，输出一行：

Escaped in x minute(s).

其中x表示逃出来所需的最短时间。

如果不可能逃出来，输出一行：

Trapped!

Sample Input
3 4 5
S…
.###.
.##…
###.#

##.##
##…

#.###
####E

1 3 3
S##
#E#

0 0 0

Sample Output
Escaped in 11 minute(s).
Trapped!

建立三维数组，广搜代码如下（bfs）：

/*6ms*/
#include<stdio.h>
struct qq
{
    int x,y,z,time;
};
struct qq que[30000];
char G[33][33][33];///三维数组，表示一个三维的地牢，分别为z，y，x轴坐标
int next[6][3]={{0,0,1},{0,1,0},{0,-1,0},{0,0,-1},{1,0,0},{-1,0,0}}; ///可以移动的6个方向
int main()
{
    int L,R,C;
    while(~scanf("%d%d%d",&L,&R,&C))
    {
    	if(L==0&&R==0&&C==0)
            break;
        /*输入*/ 
        int q,w,e,j,k,i,y=0;
        getchar();	///注意，要用getchar吸收换行符
        for(i=1;i<=L;i++){
            for(j=1;j<=R;j++){
                for(k=1;k<=C;k++){
                    scanf("%c",&G[i][j][k]);
                    if(G[i][j][k]=='S')q=i,w=j,e=k;///寻找起点位置坐标
                    if(G[i][j][k]=='E')y=1;
                }
                getchar(); ///注意，要用getchar吸收换行符
            }
            getchar(); ///注意，要用getchar吸收换行符
        }
        
        if(!y){  ///特判不存在E的情况（即没有出口的情况）
            printf("Trapped!\n");
            continue;
        }
        /*bfs搜索*/
        int head=1,tail=1,tx,ty,tz,t=0;
        que[tail].x=e,que[tail].y=w,que[tail].z=q,que[tail++].time=0;
        G[q][w][e]='#'; ///注意，起点走过也要记得标记已走过
        while(head<tail)
        {
            for(int u=0;u<6;u++){
                tx=que[head].x+next[u][2];
                ty=que[head].y+next[u][1];
                tz=que[head].z+next[u][0];
                if(tx<1||tx>C||ty<1||ty>R||tz<1||tz>L) ///越界处理
                    continue;
                if(G[tz][ty][tx]!='#'){
                    if(G[tz][ty][tx]=='E')t=1;///如果到出口，则用t标记一下，随后结束搜索
                    G[tz][ty][tx]='#'; ///标记已走过
                    que[tail].x=tx;
                    que[tail].y=ty;
                    que[tail].z=tz;
                    que[tail++].time=que[head].time+1;
                }
                if(t)break;
            }
            if(t)break;
            head++;
        }
        
        if(que[tail-1].time==0)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n",que[tail-1].time);
    }
    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69