第四章(下)

广度优先算法 Breadth First Search BFS

深度优先算法的兄弟，包含另外一种搜索思维
也叫宽度优先算法

概述

与深度优先算法不同，广度优先算法注重于”对所有情况的分析搜索”
如果是深度优先算法是刨根问底地分析每种情况，
广度优先就是在在层层扩展中找到题解

例

还是之前的问题，我们想在n*m的迷宫中找到起点到终点的最短路径

分析

我们的核心思想是分析扩展时每发现一个点，就将这个点加入到队列中，直到到达终点
另外，为防止一个点被多次走到，我们还要一个数组来记录一个点是否被走到

队列与搜索路径

我们决定使用一个队列来模拟搜索过程，我们需要：
1.两个参数x,y代表点坐标
2.一个参数s代表我们走过的步数
3.某一点之前的父，用于计算路径 （本题不需要计算路径，就省去这部分）

实现如下： 

1
2
3
4
5
struct note {
    int x ; //横坐标
    int y ; //纵坐标
    int s ; //步数
};

初始化

我们设定相关数据完成队列，并且对各个条件进行初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct node que[2501] ; //地图为50*50，设置为2501就不会越界了
int head,tail ;
int a[51][51] = {0} ; //用于存储地图    
int book[51][51] = {0} ; //记录拿一些点已经在队列中了，防止点的重复扩展 
                        //0代表还没走过

//设置队列 
head = 1 ; 
tail = 1 ;

//先将默认起点(1,1)加入
que[tail].x = 1 ;
que[tail].y = 1 ;
que[tail].s = 0 ;
tail++;
book[1][1] = 1 ;

开始搜索

我们以(1,1) -> (1,2)为例解释怎么进行点的判断
1.尝试走到(1,2)

1
2
tx = que[head].x + 0; 
ty = que[head].y + 1;

2.判断
主要是两点，一是是否越界，二是是否为障碍，三是是否已经走过

1
2
3
4
5
6
7
if(tx<1 || tx>n || ty<1 || ty >m){
    continue ; 
}

if(a[tx][ty] == 0 && book[tx][ty] == 0){
    //入队
}

入队

1
2
3
4
5
6
7
8
9
10
11
if(a[tx][ty] == 0 && book[tx][ty] == 0 ){
    //入队
    book[tx][ty] = 1 ;  //顺带一提，宽度优先中只会入队
                        //和深度优先不同，宽度优先没有把book还原的操作
    
    //插入新的点到队列中
    que[tail].x = tx ; 
    que[tail].y = ty ;
    que[tail].s = que[head].s + 1;
    tail++ ;
}

更新

我们再用相同的做法判断(2,1)，至此我们已经搜索了(1,1)周围的所有点
现在我们需要更新(1,1),这个点已经没用了，我们将它出队 

1
2
3
head++;
//利用++，直接把头部舍去，就完成了它的出队操作
//因为"已经遍历完的点"一定处于当前位置的头部，所以可以直接++

之后，我们新的出发点就变成了(1,2)，对它进行搜索，然后再更新，再搜索…直到到达终点

另外，这里的按四个方向搜索的办法和深度是一样的 

1
int next[4][2] = {  {0,1},{1,0},{0,-1},{-1,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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<stdio.h> 

struct note {
    int x ; //横坐标
    int y ; //纵坐标
    int s ; //步数

    int f ; //父编号，暂时还用不到，之后的代码请先无视f
};

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,startx,starty,p,q,tx,ty,flag ; 

    //读入参数
    scanf("%d %d",&n,&m) ;
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d %d %d %d",&startx,,&starty,&p,&q);

    //初始化队列
    head = 1 ; 
    tali = 1 ;

    //往队列插入迷宫入口坐标
    que[tail].x = startx ;
    que[tail].y = statty ;
    que[tail].f = 0 ;
    que[tail].s = 0 ;
    tail++;
    book[startx][starty] = 1 ;

    flag = 0 ; //0表示还没到达，1表示到达终点

    //当队列不为空的时候执行循环
    //为什么是“不为空”时执行，请看后面的代码

    while(head < tail){
        for(k=0;k<=3;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].f = head ; 
                que[tail].s = que[head].s +1;
                tail ++ ;
            }

            if(tx == p && ty == q){
                //如果到达目标点了，停止扩展，结束，退出循环
                flag = 1 ;
                break ;
            }
        }

            if(flag ==1)
                break ; 
            
            head++ ; //一个点拓展结束后，对后面的点再拓展
    }

    //打印步数
    //值得注意的是,tail是指向“最后一个位置的下一个位置”，因此我们要-1

    printf("%d",que[tail-1].s);

    getchar();getchar();
    return 0 ;

    }

实战

例子

我们有一个海岛，海岛有一个主岛和附属岛屿，总地图大小为10*10
我们使用0代表海洋，1-9代表路段，我们由一个点（比如(6,8)开始）算出所在岛的面积
我们想计算所在岛屿的面积

解决

我们直接利用广度搜索来进行这这件事，我们直接上了 

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

    #include <stdio.h>
    struct node{
        int x ; // 横坐标
        int y ; // 纵坐标

    };

    int main(){
        //建立搜索队列
        struct node que[2501] ; 
        int head , tail ;

        //初始化标记
        int a[51][51] ; 
        int book[51][51] = {0};

        //基础数值
        int i,j,k,sum,max = 0 ,mx,my,n,m,startx,starty,tx,ty ; 

        //定义方向数组  
        int next[4][2] = {  {0,1},  //向右
                        {1,0},  //向下
                        {0,-1}, //向左
                        {-1,0}  //向上
                        };
        
        //读入大小以及落点
        scanf("%d %d %d %d",&n,&m,&startx,&starty); 

        //读入地图
        for(i=1;i<=n:i++)
            for(j=1;j<=n;j++)
                scanf("%d",&a[i][j]);

        //队列初始化
        head = 1 ; 
        tail = 1 ;

        //加入起点坐标
        que[tail].x = startx ; 
        que[tail].y = starty ;
        tail++;
        book[startx][starty] = 1 ;
        sum = 1 ;

        //搜索开始

        //当队列不为空的时候进行循环
        while(head<tail){
            //方向列举
            for(k=0;k<=3;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){
                    sum++;

                    //每个点只入队一次，所以需要标记这个点已经走过
                    book[tx][ty] = 1 ;

                    //更新队列参数
                    que[tail].x = tx ;
                    que[tail].y = ty ;
                    tail++;
                }
            }
            //每次完成一次方向列举，我们都会搜索完四个方向的所有可能性
            //于是更新列表头，直接残酷无情的++
            head++;
            //当一个点扩展结束后，我们才能++更新
            //也只有++更新后，我们才能搜索下一个点

        }
        //最终输出
        printf("%d \n",sum);

        getchar();getchar();
        return 0 ;
    }
```  


## 水管连接
### 题干  
我们有一张N*M大小的地图  
我们想要把水管从 **(1,1)的铺设起点** 铺到 **（N,M）的铺设终点**  
其中我们有两种水管，弯管和直管，他们都可以自由地90°旋转 
其中弯管可以连接上下左右任意两个相邻位置，直管则连接相对位置    
计算连接方式，如果可以连接则输出路径，否则输出impossible

### 思路
其实本质上还是我们的深度/宽度搜索，额外添加了下面两个条件：     
1.需要考虑进出水口的方向    
2.需要给出路径  

#### 摆放情况
我们首先讨论摆放情况，有下面六种情况，我们也用1-6的编号表示它们：   
1:上到右
2:下到右
3:左到下
4:右到上
5:左到右
6:上到下

#### 状态分析
水管连接和之前的搜索比起来，最重要的一点就是条件        
那么我们先结合DFS搜索，把对应的代码写出来：     
```C
    void dfs(int x , int y , int front){
        //注意这个front，它代表的是进水口的方向
        //我们在筛选的时候以进水口方向进行一次筛选
        //1左边，2上边，3右边，4下边

        //越界判断
        if(x<1 || x>n || y<1 || y>m){
            return ; 
        }

        //判断这个点是否已经被使用过    
        if(book[x][y] ==1){
            return ; 
        }

        book[x][y] = 1 ; //还没走过的话，就先标记这里

        //先分析水管为直管的情况
        if( a[x][y] >=5 && a[x][y]<=6){
            //5 6 代表直管的两个情况

            //按照左上右下的顺序进行分析
            if(front == 1){
                dfs(x,y+1,1) ; //只能使用5号
            }

            if(front == 2){
                dfs(x+1,y,2) ; //6
            }

            if(front == 3){
                dfs(x,y-1,3) ; //5
            }

            if(front == 4){
                dfs(x-1,y,4) ; //6
            }

        }

        book[x][y] ; //因为是DFS算法，所以要记得取消标记哦
        return ; 
    }

对于弯管的处理，其原理是一样的，这里我们就不赘述了
另外，当我们到达(n,m+1)这个点时，就表明产生了完整方案——可以返回了 

1
2
3
4
5
//判断是否到达终点的Base case   
if(x==n && y==m+1){
    flag = 1 ; // 标记找到了方案
    return ; 
}

完整代码(无路径返回)

我们一步步来，先得到不返回路径，只产生方案的搜索： 

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
    #include<stdio.h>
    int a[51][51] ; 
    int book[51][51] ,n,m,flag = 0 ;
    void dfs(int x , int y , int front){
        //注意这个front，它代表的是进水口的方向
        //我们在筛选的时候以进水口方向进行一次筛选
        //1左边，2上边，3右边，4下边

        //判断是否到达终点的Base case   
        if(x==n && y==m+1){
            flag = 1 ; // 标记找到了方案
            return ; 
        }

        //越界判断
        if(x<1 || x>n || y<1 || y>m){
            return ; //碰到了就之前爬
        }

        //判断这个点是否已经被使用过    
        if(book[x][y] ==1){
            return ; //走过了那也爬
        }

        book[x][y] = 1 ; //还没走过的话，就先标记这里

        //先分析水管为直管的情况
        if( a[x][y] >=5 && a[x][y]<=6>){
            //5 6 代表直管的两个情况

            //按照左上右下的顺序进行分析
            if(front == 1){
                dfs(x,y+1,1) ; //只能使用5号
            }

            if(front == 2){
                dfs(x+1,y,2) ; //6
            }

            if(front == 3){
                dfs(x,y-1,3) ; //5
            }

            if(front == 4){
                dfs(x-1,y,4) ; //6
            }

        }

        //分析弯管，和直管原理一样  
        if( a[x][y]>=1 && a[x][y]<=4){
            if(front == 1){
                dfs(x+1,y,2) ; //3
                dfs(x-1,y,4) ; //4
            }

            if(front == 2){
                dfs(x,y+1,1) ; //1
                dfs(x,y-1,3) ; //4
            }

            if(front == 3){
                dfs(x-1,y,4) ; //1
                dfs(x+1,y,2) ; //2
            }
            
            if(front == 4){
                dfs(x,y+1,1) ; //2
                dfs(x,y-1,3) ; //3
            }
        }

        book[x][y] ; //因为是DFS算法，所以要记得取消标记哦
        return ; 
    }

    //在main方法中执行我们的方案
    int main(){
        int i,j,num = 0 ;
        scanf("%d %d",&n,&m);

        //地图读入
        for(i=1;i<=n:i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);   

        //开始搜索，从(1,1)开始
        dfs(1,1,1);

        //根据flag的最后情况分析结果
        if(flag==0)     printf("impossible \n");
        else            printf("找到了方案 \n") ; 
    }
```         
啊，“找到方案”，对，我们只是**找到了方案** 
想要让这个做法真正有意义，我们就应该**输出相应的路径**  

### 增加路径的返回
这一步比想象中简单————毕竟我们已经一步步找到了结果了    
我们只要在代码中加入一个**栈**，就可以利用它输出路径了    

```C
    struct note{
        int x ; //横坐标
        int y ; //纵坐标
    }
    s[100];

完整代码(含路径的返回)

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<stdio.h>
int a[51][51] ; 
int book[51][51] ,n,m,flag = 0 ;

//-----------------------------------------
struct note{
    int x ; //横坐标
    int y ; //纵坐标
}
s[100];
//-----------------------------------------

void dfs(int x , int y , int front){
    //注意这个front，它代表的是进水口的方向
    //我们在筛选的时候以进水口方向进行一次筛选
    //1左边，2上边，3右边，4下边

    //判断是否到达终点的Base case   
    if(x==n && y==m+1){
        flag = 1 ; // 标记找到了方案
        return ; 
    }

    //越界判断
    if(x<1 || x>n || y<1 || y>m){
        return ; 
    }

    //判断这个点是否已经被使用过    
    if(book[x][y] ==1){
        return ; 
    }

    book[x][y] = 1 ; //还没走过的话，就先标记这里

    //将标记入栈
    //-----------------------------------------
    top++ ; 
    s[top].x = x;
    s[top].y = y ;
    //-----------------------------------------

    //先分析水管为直管的情况
    if( a[x][y] >=5 && a[x][y]<=6){
        //5 6 代表直管的两个情况

        //按照左上右下的顺序进行分析
        if(front == 1){
            dfs(x,y+1,1) ; //只能使用5号
        }

        if(front == 2){
            dfs(x+1,y,2) ; //6
        }

        if(front == 3){
            dfs(x,y-1,3) ; //5
        }

        if(front == 4){
            dfs(x-1,y,4) ; //6
        }

    }

    //分析弯管，和直管原理一样  
    if( a[x][y]>=1 && a[x][y]<=4){
        if(front == 1){
            dfs(x+1,y,2) ; //3
            dfs(x-1,y,4) ; //4
        }

        if(front == 2){
            dfs(x,y+1,1) ; //1
            dfs(x,y-1,3) ; //4
        }

        if(front == 3){
            dfs(x-1,y,4) ; //1
            dfs(x+1,y,2) ; //2
        }
        
        if(front == 4){
            dfs(x,y+1,1) ; //2
            dfs(x,y-1,3) ; //3
        }
    }

    book[x][y] = 0  ; //因为是DFS算法，所以要记得取消标记哦
    //出栈---------------------------------------
    top -- ;
    //-------------------------------------------
    return ; 
}

//在main方法中执行我们的方案
int main(){
    int i,j,num = 0 ;
    scanf("%d %d",&n,&m);

    //地图读入
    for(i=1;i<=n:i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);   

    //开始搜索，从(1,1)开始
    dfs(1,1,1);

    //根据flag的最后情况分析结果
    if(flag==0)     printf("impossible \n");
    else            printf("找到了方案 \n") ; 
}