DFS/BFS简介以及剪枝技巧-DFS简介

DFS含义 ⭐

DFS，即Depth-first-search，是深度优先搜索的简称。

它的主要思路是一直沿当前分支搜索，当搜索到尽头之后返回，再逐步向其他地方扩散。

我们可以通过一个树形结构说明DFS的遍历顺序

        A
      / | \
     B  C  D
    / \    |
   E   F   G
  / \
 H   I

遍历顺序：(假设一直沿左分支走)
A→B→E→H→I→F→C→D→G

当然，完全可以沿右分支先走，甚至遍历起点并不非得是树的顶端。
事实上，DFS的实现依赖于递归，而遍历的顺序也和递归的位置息息相关。
甚至通过调整递归的顺序，我们可以用三种方法遍历一个二叉树，不过这并不是本次重点，不过多叙述
接下来让我们通过一个简单的例题来看看DFS的实现。

全球变暖

P8662 [蓝桥杯 2018 省 AB] 全球变暖

题目描述

你有一张某海域 $\times N$ 像素的照片，. 表示海洋、 # 表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

其中 “上下左右” 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 $2$ 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数 $N$ 。 $\le N \le 1000)$ 。

以下 $N$ 行 $N$ 列代表一张海域照片。

照片保证第 $1$ 行、第 $1$ 列、第 $N$ 行、第 $N$ 列的像素都是海洋。

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

7 
.......
.##....
.##....
....##.
..####.
...###.
.......

输出 #1

说明/提示

时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛

题解

这是一个连通性问题，要把图内所有联通的点都遍历一次，可以使用DFS去遍历。

DFS遍历的格式大概是

void dfs(){
    if(已遍历完){
        记录
        return;
    }
    for(...){//枚举情况
        if(遍历过)
            continue;
        记录此点
        dfs();
        回溯
    }
}

观察可知，此题需要我们不断向四周扩散记录联通区域。
解题思路大概是：
先对输入数据预处理，令我们可以通过二维数组中的值得知这块陆地周围有几个岛屿。
然后每次检查，都把一整片岛屿标记为已检查，在这个过程中寻找有没有周围有四块陆地的点。如果有，说明这个岛屿不会被淹没。

而这个检查的过程就可以通过DFS递归来实现：
每次检查完一块陆地都检查这块陆地周围的陆地有没有 $4$
最后达到同时遍历一整块岛屿的效果。

其中，关键在于DFS递归时的退出条件以及正确清空已经遍历过的岛屿，避免死循环。

代码

#include<iostream>
using namespace std;
int map[1002][1002]={0};
void doo(int i,int j){
    if(map[i][j-1])
        map[i][j]++;
    if(map[i][j+1])
        map[i][j]++;
    if(map[i+1][j])
        map[i][j]++;
    if(map[i-1][j])
        map[i][j]++;
}
void check(int i,int j,bool&flag){
    if(map[i][j]==0)
        return;
    if(map[i][j]==5)
        flag=1;
    map[i][j]=0;
    check(i+1,j,flag);check(i-1,j,flag);check(i,j+1,flag);check(i,j-1,flag);
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            char temp;
            cin>>temp;
            if(temp=='#')
                map[i][j]=1;
            else
                map[i][j]=0;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(map[i][j]==0)
                continue;
            doo(i,j);
        }
    int ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(map[i][j]==0)
                continue;
            bool flag=0;
            check(i,j,flag);
            if(flag==0)
                ans++;
        }
    cout<<ans;
    return 0;
}

DFS练习题目：建议看完剪枝技巧再做其中难度较高的题
P1219八皇后
P1019单词接龙
P5194 Scales S

秒客网