DFS和BFS

DFS

通过题目来对DFS回溯法进行了解

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N =10;
int path[N];//记录路径的数组
int state[N];//判断是不是用了
int n;
void dfs(int u){
	if(u>n){
		for(int i = 1;i<=n;i++){
			cout<<path[i]<<' ';
		}
		cout<<'\n';
	}
	for(int i = 1;i<=n;i++){
		if(!state[i]){//如果这个数字没有被用
			path[u] = i;
			state[i] = 1;
			dfs(u+1);//深搜
			path[u] = 0;//恢复现场
			state[i] = 0;
		}
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	dfs(1);
}

---

对于DFS我们可以看出这是一条路走到黑的，然后当我们碰壁后，就需要原路返回，也就是需要做到恢复现场的操作。也就是回到一开始的状态。

bfs的基本操作，bfs是可以找到最短路径的，但是dfs是不一定能找到最短路径的。

题目 走迷宫

给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。数据保证(1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路

输入样例

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

---

代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
constexpr int N = 110;
typedef pair<int,int> PII;
int g[N][N];//存储地图
int f[N][N];//存储距离
int n,m;
void bfs(int a,int b){
	queue<PII> q;
	q.push({a,b});//横坐标和纵坐标
	f[0][0] = 0;
	while(!q.empty()){
		PII start = q.front();//读取队列顶端的
		q.pop();
		int dx[4] = {0,1,0,-1};//四个方向下，右，上，左
		int dy[4] = {-1,0,1,0};
		for(int i = 0;i<4;i++){
			int x = start.first+dx[i];
			int y = start.second+dy[i];
			if(g[x][y]==0){//如果没有找到就走过去
				g[x][y] = 1;
				f[x][y] = f[start.first][start.second]+1;//距离加1
				q.push({x,y});
			}
		}
	}
	cout<<f[n][m];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(g,1,sizeof(g));
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin>>g[i][j];
		}
	}
	bfs(1,1);
}

所以BFS是操作是用队列来存储，首先存储要开始的地方，然后读取队列顶端，然后往下走，走到下一个不是1的位置然后就可以读入队列中，并且将走过0的位置标记成1。