穷竭搜索——深度优先搜索(dfs)

综述

深度优先搜索(DFS)是搜索的方式之一。它是从某个状态开始，不断地进行状态转移，直到无法转移为止。

然后回溯到前一步，再次重复进行状态转移，直到遍历所有的情况。一般来说，使用递推函数比较简单。

例题1：判断是否存在和为定值

（题目转载自洛谷）

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
//给定整数a1,a2,...,an，判断是否可以从中选出若干数，使它们的和恰好为k。
//限制条件：1 <= n <= 20;
//样例：
//输入:n = 4   a = {1,2,4,7}    k = 13
//输出:Yes

#include<iostream>
using namespace std;
int n,k,i = 0;
int a[25];
int main() {
	cout << "n = ";
	cin >> n;
	cout << "a = {";
	while (cin >> a[i]) {
		i++;
		if (i == n)
			break;
	}
	cout << "k = ";
	cin >> k;
    //使用深搜方法
		bool dfs(int i, int sum);
		if (dfs(0, 0))
			cout << "Yes" << endl;
		else cout << "No" << endl;
		system("pause");
		return 0;

}
//从a1开始决定每个数加不加到sum里，等n个数全部都决定后，再判断是否等于k
bool dfs(int i,int sum){
	if (i == n)			//穷竭后判断是否等于k
		return sum == k;
	if (dfs(i + 1, sum))//不加上a[i]的情况，判断最终是否等于k
		return true;
	if (dfs(i + 1, sum + a[i]))//加上a[i]的情况，判断是否等于k
		return true;
	
	return false;//无论加不加，都不等于k，返回false
}

例题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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//一矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为
//沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
//输入格式
// 第一行两个整数代表矩阵大小n和m。
// 接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个 n×m 的矩阵。
// 1≤n,m≤100
// 
//输入：
// 4 10
//0234500067
//1034560500
//2045600671
//0000000089
//输出:4

#include<iostream>
using namespace std;
int n, m;
int cont = 0;
int map[100][100];//地图数组
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf_s("%1d",& map[i][j]);//使用scanf是因为可以控制读入的位数
		}
	}
	void dfs(int x, int y);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] != 0) {	//
				dfs(i, j);
				cont++;
			}

		}
	}
	printf("%d", cont);
	return 0;
}
//搜寻map[x][y]紧邻的所有数字，将他们全部变为0
void dfs(int x, int y) {
	int dx[]{ 0,0 ,1,-1};
	int dy[]{ 1,-1,0,0 };//方位数组
	map[x][y] = 0;		 //赋值0
	for (int i = 0; i < 4; i++) {
		x += dx[i];
		y += dy[i];
		if (map[x][y] != 0 && x >= 0 && x < n && y >= 0 && y < m) {
			dfs(x, y);	//如果转变状态后，没有超过边界，并且不等于0，就继续深搜
		}
		x -= dx[i];		//直到超过边界，或者遇到0数字，就回溯
		y -= dy[i];
	}
}

例题3：拯救oibh总部

（题目转载自洛谷）

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
//dfs第三题 拯救oibh总部
//oibh被突来的洪水淹没了 > . < 还好oibh总部有在某些重要的地方起一些围墙，
//用* 号表示，而一个封闭的* 号区域洪水是进不去的……现在给出oibh的围墙建设图，
//问oibh总部没被淹到的重要区域（由"0"表示）有多少。
//
//	输入格式
//	第一行是两个数，x和y（x, y <= 500）
//
//	第二行及以下是一个由 * 和0组成的x * y的图。
//
//	输出格式
//	输出没被水淹没的oibh总部的“0”的数量。

//输入样例：
//4 5
//00000
//00*00
//0*0*0
//00*00
//输出样例：1
#include<iostream>
using namespace std;
char map[510][510];//地图char型数组
int m, n, cont = 0;
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };//方位数组
void dfs(int x, int y) {
	if (x < 0 || y < 0 || x > m + 1 || y > n + 1 || map[x][y] == '*')//边界
        //特别注意：这里为什么不是x<=0||y<=0||x>=m+1||y>=n+1，因为要多深搜一圈。
		return;//结束函数
	map[x][y] = '*';
	for (int i = 0; i < 4; i++) {
		dfs(x + dx[i], y + dy[i]);
	}
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0, 0);//将*外所有的0全都变为*
			  //注：方法一：多深搜一圈，从(0,0)开始，而不是(1,1)，为保证能遍历所有*外的0。
				  /*方法二：每条边都搜一遍*/
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (map[i][j] == '0')
				cont++;
		}
	}
	cout << cont << endl;
	return 0;
}

例题4：Lake Counting S

（题目转载自洛谷）

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
//dfs第四题 Lake Counting S
//由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1 <= N <= 100; 1 <= M <= 100)网格图表示。
//每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。
//约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
//输入格式
//第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。字符之间没有空格。
//输出格式
//一行：水坑的数量
//输入样例：				输出样例：3
//10 12
//W........WW.
//.WWW.....WWW
//....WW...WW.
//.........WW.
//.........W..
//..W......W..
//.W.W.....WW.
//W.W.W.....W.
//.W.W......W.
//..W.......W.

#include<iostream>
using namespace std;

char ma[110][110];//地图数组
int m, n;
int cont = 0;
void dfs(int x, int y) {
	if (x < 0 || x >= m || y < 0 || y >= n || ma[x][y] == '.')//边界
		return;
	ma[x][y] = '.';
	int dx[]{ 0,0,1,1,1,-1,-1,-1 };//方位数组
	int dy[]{ 1,-1,0,-1,1,1,0,-1 };
	for (int i = 0; i < 8; i++) {
		dfs(x + dx[i], y + dy[i]);
	}
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> ma[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (ma[i][j] == 'W') {
				cont++;
				dfs(i, j);
			}

		}
	}
	cout << cont;
	return 0;
}