[数据结构与算法]【暑期集训第一周：搜索】【DFS&&BFS】

一、深度优先搜索（DFS）

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。一条道走到黑

1.1 全排列问题

1.1.1 问题描述

按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 $n$。

输出格式

由 $1～n$ 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 $5$ 个场宽。

样例 #1

样例输入 #1

3

样例输出 #1

1    2    3
1    3    2
2    1    3
2    3    1
3    1    2
3    2    1

$1\le n\le 9$。

1.1.2 思路表示

DFS+回溯+剪枝

先定义两个数组，一个是用来存放解的，一个是用来标记该数是否用过。

接下来就是写深搜的函数了。主要思路：

先判断格子是否填满了，如果填满，则输出一组全排列；如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填入，搜索下一格。

1.1.3 代码

#include <bits/stdc++.h>
using namespace std;
int n;
int print[100];
bool tag[100];
void dfs(int m){
    if (m == n){
        for (int j = 0; j < n; j++){
            printf("%5d", print[j]);
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++){
        if (tag[i])//如果这个数标记过，则不能使用
            continue;
        tag[i] = true;//先标记再使用
        print[m] = i;
        dfs(m + 1);
        tag[i] = false;//回溯
    }
}
int main(){
    cin >> n;
    dfs(0);
}

二、广度优先搜索（BFS）

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。每一个点都向外拓展搜索

（源自OIWIKI）

// C++ Version
void bfs(int u) {
  while (!Q.empty()) Q.pop();
  Q.push(u);
  vis[u] = 1;
  d[u] = 0;
  p[u] = -1;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      if (!vis[e[i].to]) {
        Q.push(e[i].to);
        vis[e[i].to] = 1;
        d[e[i].to] = d[u] + 1;
        p[e[i].to] = u;
      }
    }
  }
}

void restore(int x) {
  vector<int> res;
  for (int v = x; v != -1; v = p[v]) {
    res.push_back(v);
  }
  std::reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); ++i) printf("%d", res[i]);
  puts("");
}

具体来说，我们用一个队列 Q 来记录要处理的节点，然后开一个布尔数组 vis[] 来标记是否已经访问过某个节点。

开始的时候，我们将所有节点的 vis 值设为 0，表示没有访问过；然后把起点 s 放入队列 Q 中并将 vis[s] 设为 1。

之后，我们每次从队列 Q 中取出队首的节点 u，然后把与 u 相邻的所有节点 v 标记为已访问过并放入队列 Q。

循环直至当队列 Q 为空，表示 BFS 结束。

在 BFS 的过程中，也可以记录一些额外的信息。例如上述代码中，d 数组用于记录起点到某个节点的最短距离（要经过的最少边数），p 数组记录是从哪个节点走到当前节点的。

有了 d 数组，可以方便地得到起点到一个节点的距离。

有了 p 数组，可以方便地还原出起点到一个点的最短路径。上述代码中的 restore 函数使用该数组依次输出从起点到节点 x 的最短路径所经过的节点。

2.1 填涂颜色

2.1.1 题目描述

由数字 $0$ 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 $1$ 构成，围圈时只走上下左右 $4$ 个方向。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 6$ 的方阵（$n=6$），涂色前和涂色后的方阵如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 $n(1\le n\le 30)$。

接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n\times n$ 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 $0$。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式

已经填好数字 $2$ 的完整方阵。

样例 #1

样例输入 #1

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

样例输出 #1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

提示

对于 $100\%$ 的数据，$1\le n\le 30$。

2.1.2 解题思路

BFS

按照广搜的思路，每次拓展不在封闭区域内的0，然后标记，最后没有被标记的0就是要涂色的点。

2.1.3 代码

int xx[] = {0, 1, 0, -1};//方向向量
int yy[] = {1, 0, -1, 0};

int mp[40][40];//图
bool vis[40][40];//是否搜索到

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> mp[i][j];//读图
    queue<pair<int, int>> q;
    q.push({0, 0});//搜索起点
    vis[0][0] = 1;
    //bfs
    while (!q.empty()){//当队列不为空
        for (int i = 0; i < 4; i++){//四个方向
            int dx = q.front().first + xx[i];
            int dy = q.front().second + yy[i];
            if (dx <= n + 1 && dy <= n + 1 && dx >= 0 && dy >= 0 && mp[dx][dy] == 0 && !vis[dx][dy]){
            //如果在区域内，且没有被标记过，且mp[][]=0
                q.push({dx, dy});//入队
                vis[dx][dy] = 1;//标记
            }
        }
        q.pop();//出队
    }
    //bfs--end
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (mp[i][j] == 0 && vis[i][j] == 0)//没有标记过且mp[][]=0
                cout << 2;
            else
                cout << mp[i][j];
            cout << " ";
        }
        cout << endl;
    }
}