写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

DFS（深度优先搜索）

往深处搜索，触底返回，遇到新的分叉口继续往深处搜素。如图所示。

解题关键： 回溯+剪枝。要考虑顺序。 回溯：在触底之后返回父节点，并将使用过的地方返回原样。（用递归实现） 剪枝：在父节点判断，如果下面的子节点已经不满足题意（或者已经不是最优解），那么直接跳过下面的子节点，寻找新的路径。

举个例子：

1.搜索n个数字的全排列组合方式，并输出所有情况。例如输入2，输出1 2和2 1.

解题思路：

使用DFS需要一位一位的搜索，比如说如果两位，就要先确认第一位，再确认第二位。递归返回的时候把用过的一位恢复成0。

下面是模板：

#include <iostream>
#include <cstdio>

using namespace std;
int  path[10];
bool flag[10];
int n;
void dfs(int x)
{
    if(x==n)//如果已经指向了n后面的一位，那么搜索结束，输出结果
    {
        for(int i=0; i<n; i++)
            printf("%d ",path[i]);
        puts("");
        return;
    }

    for(int i=1; i<n+1; i++)
    {
        if(!flag[i])
        {
            path[x]=i;
            flag[i]=true;
            dfs(x+1);//递归算下一位的数字
            flag[i]=false;//递归结束恢复初始状态
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);//从第0个位置开始填坑
    return 0;
}

2. n皇后问题。在n * n的棋盘上有n个皇后，她们不在同一列，同一行，同一对角线上。输出皇后一共有多少种摆放方式。（用‘.’代表空格，‘Q’代表皇后）

本道题有两种解法。

第一种解法：

1. 第一种解法和上一道题类似。经过分析得出，每列只能有一个皇后，所以每列搜到一个皇后即可停止。
2. 在上述条件下，只需判断待判断空格和其他皇后是否在对角线上即可。

判断是否在对角线上的方法：

可以把棋盘看做方程，然后用解方程的思路推断求解。

下面是模板：

#include <iostream>
#include <cstdio>
const int N=20;
using namespace std;
char  sam[N][N];
bool flag[N],bg[N],gb[N];
int n;
void dfs(int x)
{
    if(x==n)//如果已经指向了n后面的一位，那么搜索结束，输出结果
    {
        for(int i=0; i<n; i++)
            puts(sam[i]);
        puts("");
        return;
    }

    for(int i=0; i<n; i++)
    {
        if(!flag[i]&&!bg[i+x]&&!gb[i-x+n])
        {
            sam[x][i]='Q';//也是一行一行查找，n行就有n个空格需要填满
            flag[i]=bg[i+x]=gb[i-x+n]=true;
            dfs(x+1);//递归算下一位的数字
            flag[i]=bg[i+x]=gb[i-x+n]=false;//递归结束恢复初始状态
            sam[x][i]='.';
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        sam[i][j]='.';
    dfs(0);//从第0个位置开始填坑
    return 0;
}

第二种解法：

这种方法更接近最原始的思维，即一个格子一个格子的询问是否满足条件从而放皇后，判断是否为对角线的方法和第一种类似。

下面是模板：

#include <iostream>
#include <cstdio>
using namespace std;
const int N=20;//暴力解决
int n;
char sam[N][N];
bool hang[N],lie[N],bg[N],gb[N];

void dfs(int x,int y,int num)//num表示第几位
{
    if(y==n) y=0,x++;//y是列x是行
    if(x==n)
    {
        if(num==n)
        {
            for(int i=0; i<n; i++)
                puts(sam[i]);
            puts("");
        }
        return;
    }

    //该格子不能放入皇后

    dfs(x,y+1,num);

    //放皇后

    if(!hang[x]&&!lie[y]&&!bg[y+x]&&!gb[y-x+n])
    {
        sam[x][y]='Q';
        hang[x]=lie[y]=bg[y+x]=gb[y-x+n]=true;
        dfs(x,y+1,num+1);//放进去了个数要加一
        hang[x]=lie[y]=bg[y+x]=gb[y-x+n]=false;
        sam[x][y]='.';

    }

}


int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            sam[i][j]='.';

    dfs(0,0,0);

    return 0;
}

BFS（宽度优先搜素）

一层一层搜索，找到答案停止，答案一定是离树根最近的点。

举个例子：

走迷宫，用‘0’代表可行，‘1’代表不可行，倒序输出最短路经过的坐标和最短路一共的步数。

解题思路：

1. 首先要从入口入手，判断四周的点是否可走，是否使用过（使用过的点1一定不会是最短路径）。
2. 重复以上步骤，知道步数已经超过走到重点的步数。

下面是模板：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;



const int N=110;
typedef pair <int ,int >PII;//存坐标
int n,m;
int ditu[N][N];
int shiyong[N][N];
PII q[N*N],shunxu[N][N];

int bfs()
{
    int hh=0,tt=0;
    q[0]={0,0};//模拟队列

    memset(shiyong,-1,sizeof shiyong);
    shiyong[0][0]=0;

    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};//模拟方向坐标

    while (hh<=tt)//队列存在
    {
        auto t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];//四个方向依次判断
            if(x>-1&&x<n&&y>-1&&y<n&&ditu[x][y]==0&&shiyong[x][y]==-1)//判断下一个数字是否在迷宫范围内以及是否满足第一次使用的条件
            {
                shiyong[x][y]=shiyong[t.first][t.second]+1;
                shunxu[x][y]=t;
                q[++tt]={x,y};
            }
        }
    }
    int x=n-1,y=m-1;
    while (x||y)//xy都不为0
    {

        cout<<x <<" "<<y<<endl;
        auto t=shunxu[x][y];
        x=t.first,y=t.second;
    }

    return shiyong[n-1][m-1];
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
    {
        scanf("%d",&ditu[i][j]);
    }
    int num=bfs();
    cout << num<<endl;
    return 0;
}

DFS和BFS的区别：