搜索问题 DFS BFS
DFS
dfs更多用于解决存在性问题和遍历性问题
他可以很容易找到一个东西是否存在，比如说一条路径是否存在，不需要恢复现场
也可以比较方便的展示所有的情况，比如说遍历所有的全排列，需要恢复现场
排列数字
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
读完题就知道这是一个展示全排列的问题
dfs的本质就是遍历所有的情况，因此我们首先应该明确一下所有情况的遍历方法
这里是要展示n个数字，我们可以理解为n个格子
例如n=3，我们首先考虑第一个格子放什么，比如说1，那现在的情况就是 1 _ _ ，因为是深度优先，继续往下走，1 2 _ （或者是 1 3 _）
如果是1 2 _ 那结果就是 1 2 3，此时到底，回溯
回到1 2 _ 除了3，没有别的可以再放（st数组）
再回溯
回到1 _ _，可以有1 3 _
继续往下遍历
事实上，在具体实现的时候我们使用的就是递归对于每个位置，遍历当前的情况，如果没有使用过（st数组为false）就dfs下一层
但是需要注意的是退出情况是递归到最后一层的下一层，比如说，一共有n层，从0开始，u记录层数，那么就是u=n的时候退出。
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
void dfs(int u)
{
//退出情况 第n-1层放完，第n层没有放
if(u==n)
{
for(int i=0;i<n;i++)
{
cout<<path[i]<<" ";
}
cout<<endl;
return;//注意这里是基线情况，需要退出
}
//不需要退出，就枚举每一个数字
for(int i=1;i<=n;i++)
{
//如果没被用过，就可以放到这个位置上
if(!st[i])
{
//在path中记录，st中标记使用过
path[u]=i;
st[i]=true;
//进行下一个深度的遍历
dfs(u+1);
//下一个深度结束了，针对该位置要进行后续的for，应该首先恢复现场
path[u]=0;
st[i]=false;
}
}
}
int main()
{
// int n;
cin>>n;
dfs(0);
return 0;
}
n皇后问题
BFS
bfs更多用于处理最短等情况，因为他在扩展的时候可以记录每条路的长度，天然适配与长度有关的问题
走迷宫
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角(n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m)处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
这道题就很适合用bfs来处理，只需要在扩展的时候记录下每个点到起点的距离即可
bfs的基本模式如下
-
用一个队列来存储点 这个点通常用pair来表示，因此队列里面的东西也是成对的pair
-
将起点放入队列
-
如果队列不空
-
每次从队列中取出队头元素 q.front 扩展其子节点
-
对子节点进行判断，符合条件的子节点再入队
-
同时修改我们需要存储的东西，对于这道题，我们需要记录每个点是否被走过，这里我们不需要担心有没有可能一个点被路线A走过以后，标记为走过，路线B就走不了了，但是路线B是最短路。事实上是不会出现这种情况，因为扩展A B时，两者是同时扩展，可以认为是走的步数一样，如果有某个点是上述情况，那么假设B是最短路，那么A先走到这个点，，A沿着B之后路线继续走到终点，并且A在这个点之前的路比B更短，因此A才是最短路，所以矛盾了。
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N];
bool st[N][N];
int d[N][N];
typedef pair<int,int> PII;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
queue<PII> q;
q.push({0,0});
while(!q.empty())
{
PII t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>=0 && x<n && y>=0 && y<m && !st[x][y] && a[x][y]==0)
{
q.push({x,y});
d[x][y]=d[t.first][t.second]+1;
st[x][y]=true;
}
}
}
cout<<d[n-1][m-1];
}