深度优先搜索DFS

DFS

DFS与BFS区别

1.DFS优先往深处走，无路可走了就回溯，回溯的同时还会看是否可以往深处走，不然就再回溯。

2.DFS使用的数据结构是stack。

3.DFS的空间复杂度是o(h)，相比BFS有优势。

4.不具有最短路的性质

每个DFS都对应一个搜索树

DFS俗称暴搜，总重要的是顺序，思考用什么顺序遍历所有方案

例题1.排列数字

例题1
1
2
3
4
5
6
7
8
9
10
11
12
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1≤n≤7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; 
bool st[N]; //判断数有没有被用过 

void dfs(int u){
	if(u == n){//当u等于n的时候，所有位置都被填满，输出 
		for(int i = 0; i < n; i++) printf("%d ", path[i]);
		puts(""); 
		return;
	}
	
	for(int i = 1; i <= n; i++){
		if(!st[i]){
			path[u] = i;
			st[i] = true;//记录i已经被用过了 
			dfs(u + 1);	//递归处理
			st[i] = false;//恢复状态 
		}
	}
	
}

int main(){
	cin >> n;
	
	dfs(0);
	
	return 0; 
}

例题2.n皇后问题

例题2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9

输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//----------------------------搜索思路一：找到能放皇后的位置然后放皇后--------------------------

#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];//同一列，正对角线diagonal,反对角线 

void dfs(int u){
	if(u == n){
		for(int i = 0; i < n; i++) cout<<g[i]<<endl;
		cout<<endl;
		return;
	}
	
	for(int i = 0; i < n; i++){
		if(!col[i] && !dg[u + i] && !udg[u - i + n]){
			//对角线的坐标用与y轴的截距表示，y=-x+b,b=x+y，所以是u+i 
			//y=x+b,b=y-x，但因为数组的下标不能是负数，所以加一个偏移量n
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[u - i + n] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[u - i + n] = false;
			g[u][i] = '.';
		}
	}
}

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

//------------------------搜索思路二：从第一个格子开始判断能不能放皇后---------------------------
//这种搜索方法更加原始，也更慢，比第一种方法慢了五倍左右
#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s){//x表示行，y表示列， s表示皇后已经放了几个 
    
    if(y == n) y = 0, x++;
	
	if(x == n){
	    if(s == n) {
		    for(int i = 0; i < n; i++) cout << g[i] << endl;
		    cout << endl;
	    }
        return;
	}
	

	//放皇后
	if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){
		g[x][y] = 'Q';
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
		dfs(x + 1, 0, s + 1);
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
		g[x][y] = '.';
	} 
	
	//不放皇后
	dfs(x, y + 1, s);
	
}

int main(){
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			g[i][j] = '.';
		}
	}
	
	dfs(0, 0, 0);
	
	return 0;
}

宽度优先搜索BFS

BFS

BFS与DFS区别

1.BFS是先将最近的一层全走遍后，再向深处走一点，再走遍全层，再往深走。

2.BFS使用的数据结构是queue。

3.BFS的空间复杂度是o(2^h)，相比DFS有劣势。

4.具有最短路的性质（第一次搜到的点一定是最近的点）

例题3.走迷宫

例题3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
给定一个 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//--------------------------手动实现队列-----------------------------
#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N];//g数组存的是地图
int d[N][N];//d数组存的是每个点到起点的距离
PII q[N * N];

int bfs(){
	int hh = 0, tt = 0;
	q[0] = {0, 0};
	
	memset(d, -1, sizeof d);//将d数组初始化为-1，表示没有走过 
	d[0][0] = 0;//表示起点已经走过了
	
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, 1, 0, -1};//方位数组 
	
	while(hh <= tt){//当队列不空 
		auto t = q[hh++]; //每次取出队头 
		//向上下左右扩展 
		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 && g[x][y] == 0 && d[x][y] == -1){
				//当这个点没有超出边界，并且这个点是空地可以走，并且没有走过
				d[x][y] = d[t.first][t.second] + 1;//在上个点的基础上距离加1 
				q[ ++ tt] = {x, y};//把刚走到的点加到队列中 
			}
		}
	} 
	return d[n - 1][m - 1];
}

int main(){
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> g[i][j];
		}
	}
	
	cout << bfs() << endl;
	return 0;
} 
//-------------------------------STLqueue---------------------------------
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
queue<PII> q;
int g[N][N];
int d[N][N];

int bfs(){
	q.push({0, 0});
	
	memset(d, -1, sizeof d);
	d[0][0] = 0;
	
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, 1, 0, -1};
	while(!q.empty()){
		
		auto 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 && g[x][y] == 0 && d[x][y] == -1){
				d[x][y] = d[t.first][t.second] + 1;
				q.push({x, y});
			}
		}
	}
	return d[n - 1][m - 1];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> g[i][j];
		}
	}
	
	cout << bfs() <<endl;
	
	return 0;
}