叠甲：鄙人水平有限，本文为作者的学习总结，仅供参考。
1. 搜索介绍
2. DFS 与 BFS 的区别
| 类别 | DFS | BFS |
|---|---|---|
| 搜索类型 | 试探搜索 | 地毯搜索 |
| 所用的数据结构 | 栈（vector也是可以的） | 队列 |
| 适用的题目 | 求方案总数 | 求最短路径 |
| 实现方法 | 一般结合回溯算法一同实现 | 将可行行方案放入队列，然后一一遍历 |
3. 举些栗子
3.1 BFS--马的遍历
题目描述
有一个 $ n * m $ 的棋盘，在某个点 $ (x, y (x,y $上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
【1】 构建对应结构体与队列
【2】 初始化数据和初始点
【3】 根据初始点与遍历关系遍历其它符合要求的点
【4】 查询答案
#include <bits/stdc++.h>
#define N_MAX 400
using namespace std;
int mp[N_MAX][N_MAX]; // mp[i][j] 表示马到（i，j）点所需的最少次数
int n,m,x,y;
// 定义 dx dy 便于运算
int dx[] = {-1,1,2,2,1,-1,-2,-2};
int dy[] = {-2,-2,-1,1,2,2,1,-1};
// [1] 定义数据结构体与duilie
struct point{
int x,y; // 点的坐标
int t; // 马到该点的最少次数
};
queue<point> que;
int main(
{
// [2] 初始化数据
memset(mp,-1,sizeof(mp;
cin >> n >> m >> x >> y;
mp[x][y] = 0; // 初始点为 0
// [3] 搜索
que.push((point{x,y,mp[x][y]}; // 先向队列中压入初始点
while(!que.empty(
{
// 从队列中一个一个的遍历
point p = que.front(;
que.pop(; // 记得弹出
// 寻找满足条件的点,并压入队列中
for(int i = 0;i < 8;i++
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
// 判断是否合法
if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == -1
{
mp[nx][ny] = p.t + 1;
que.push((point{nx,ny,mp[nx][ny]};
}
}
}
// 输出结果
for(int i = 1;i <= n;i++
{
for(int j = 1;j <= m;j++
{
cout << mp[i][j] << " ";
}
cout << endl;
}
return 0;
}
3.2 BFS--奇怪的电梯
题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 \(i\ 层楼（\(1 \le i \le N\）上有一个数字 \(K_i\（\(0 \le K_i \le N\）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： \(3, 3, 1, 2, 5\ 代表了 \(K_i\（\(K_1=3\，