DFS常见模板题

地图型

1. POJ 2386 Lake Counting

/******************** Lake Counting POJ 2386 http://poj.org/problem?id=2386 ********************/

# include <iostream>
# include <string>
# include <cstdio>

int n;
int m;
const int maxn = 105;
char field[maxn][maxn];

bool check(int nx, int ny) {
   
	return 0 <= nx && nx < n && 0 <= ny && ny < m && field[nx][ny] == 'W';
}

void dfs(int x, int y) {
   
	field[x][y] = '.';
	
	for (int dx = -1; dx <= 1; dx++) {
   
		for (int dy = -1; dy <= 1; dy++) {
   
			int nx = x + dx;
			int ny = y + dy;
			
			if (check(nx, ny)) {
   
				dfs(nx, ny);
			}
		}
	}
}

int main() {
   
	std::cin >> n >> m;
	std::cin.ignore(1, '\n');
	for (int i = 0; i < n; i++) {
   
		scanf("%s", field[i]);
	}
	
	int res = 0;
	for (int i = 0; i < n; i++) {
   
		for (int j = 0; j < m; j++) {
   
			if (field[i][j] == 'W') {
   
				dfs(i, j);
				res++;
			}
		}
	}	
	
	printf("%d\n", res);
	
	return 0;
}

2. [蓝桥杯2016决赛]路径之谜

# include <iostream>
# include <cstdio>

int n;
const int N = 25;
int row[N];
int col[N];
int pos[N][N];
bool vis[N][N];

int dx[4] = {
   1, 0, -1, 0};
int dy[4] = {
   0, -1, 0, 1};

int srow = 0;
int scol = 0;

int print[N * N];
int k = 1;

bool check(int x, int y) {
   
	return srow && scol && 1 <= x && 1 <= y && x <= n && y <= n && !vis[x][y] && row[y] && col[x];
}

void init() {
   
	int t = 0;
	for (int i = 1; i <= n; i++) {
   
		for (int j = 1; j <= n; j++) {
   
			pos[i][j] = ++t;
		}
	}
}

void dfs(int x, int y) {
   
	if (x == n && y == n) {
   
		if (srow == 0 && scol == 0) {
   
			for (int i = 1; i <= k; i++) {
   
				printf("%d ", print[i] - 1);
			}

			return;
		}
	}

	for (int i = 0; i < 4; i++) {
   
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		if (check(nx, ny)) {
   
			vis[nx][ny] = true;
			row[ny]--;
			col[nx]--;
			srow--;
			scol--;
			print[++k] = pos[nx][ny];
			
			dfs(nx, ny); 
			
			k--;
			row[ny]++;
			col[nx]++;
			srow++;
			scol++;
			vis[nx][ny] = false;
		}
	}
}

int main() {
   
	scanf("%d", &n);
	init();

	for (int i = 1; i <= n; i++) {
   
		scanf("%d", &row[i]);
		srow += row[i];
	}

	for (int i = 1; i <= n; i++) {
   
		scanf("%d", &col[i]);
		scol += col[i];
	}

	srow--;
	scol--;
	row[1]--;
	col[1]--;
	print[1] = 1;
	vis[1][1] = 1;

	dfs(1, 1);

	return 0;
}

数据型

1. WIT OJ 1468 Operator

一个长度为n的整数数组A，在每两个数之间填入 ‘+’ 或者 ‘-’, 使得最终运算结果尽可能接近给定的评估值 k.
共有n-1个运算符，运算符为’+‘或者’-’.

可以用oper数组将途径的运算符进行标记，递归结束时计算sum值。复杂度$O(2^n)$

# include <iostream>
# include <cstdio>
# include <cmath>

int n, k;
int a[25];
bool oper[25];
int val;

void dfs(int step) {
   
	if (step >= n) {
   
		int sum = a[1];
		for (int i = 1; i < n; i++) {
   
			if (!oper[i]) {
   							
				sum += a[i+1];
			} else {
   
				sum -= a[i+1];
			}
		}
		
		val = std::min(val, abs(sum - k));
		
		return;
	}
	
	oper[step] = 0;
	dfs(step + 1);
	
	oper[step] = 1;
	dfs(step + 1);
}

int main() {
   
	int T;
	std::cin >> T;

	while (T--) {
   
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++) {
   
			scanf("%d", &a[i]);
		}
		
		val = 0x3f3f3f3f;
		
		dfs(1);
		printf("%d\n", val);
	}
	
	return 0;
}

也可以将sum作为参数直接进行递归。此方法耗时更少。

# include <iostream>
# include <cstdio>
# include <cmath>

int n, k;
int a[25];
int val;

void dfs(int step, int sum) {
   
	if (step >= n + 1) {
   
		val = std::min(val, abs(sum - k));
		return;
	}
	
	dfs(step + 1, sum + a[step]);
	dfs(step + 1, sum - a[step]);
	
	return;
}

int main() {
   
	int T;
	std::cin >> T;
	while (T--) {
   
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++) {
   
			scanf("%d", &a[i]);
		}

		val = 0x3f3f3f3f;
		dfs(2, a[1]);
		printf("%d\n", val);
	}
	
	return 0;
}

总结：常规的DFS处理数据可以选择用1个参数且保存路径，在递归结束时根据路径求出结果，也可以将所需要求的结果作为另一个参数不保存路径。

2. 部分和问题

一个长度为n的整数数组a，判断是否可以从中选出若干数，使得它们的和恰好为k。

# include <iostream>
# include <cstdio>

int n;
int k;
int a[25];
bool vis[25];

bool dfs(int step, int sum) {
   
	if (sum > k) {
   
		return false;
	}
	
	if (step >= n) {
   
		return sum == k;
	}

	vis[step] = false;
	if (dfs(step + 1, sum)) {
   
		return true;
	}

	vis[step] = true;
	if (dfs(step + 1, sum + a[step])) {
   
		return true;
	}
	
	return false;
}

int main() {
   
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
   
		scanf("%d", &a[i]);
	}

	scanf("%d", &k);

	if (dfs(0, 0)) {
   
		printf("Yes\n");

		for (int i = 0; i < n; i++) {
   
			if (vis[i])
				printf("%d ", a[i]);
		}
	} else {
   
		printf("No\n");
	}
	
	return 0;
}

3. 蓝桥杯2015初赛 牌型种数

一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序, 自己手里能拿到的初始牌型组合一共有多少种？

方法一：sum代表目前手中的卡牌张数，step代表目前手中的卡牌点数，cnt代表当前卡牌点数在手中的数量，卡牌点数大于13时剪掉，当前卡牌点数在手中的数量大于4时剪掉，但不加方案数。

# include <iostream>

typedef long long ll;
ll ans;
int cnt;

void dfs(int sum, int step) {
   
	if (cnt > 4) {
   
		return;
	}

	if (sum == 13) {
   
		++ans;
		return;
	}

	if (sum > 13) {
   
		return;
	}

	for (int i = step; i >= 1; i--) {
   
		cnt++;
		dfs(sum + 1, i);
		cnt = 0;
	}
}

int main() {
   
	dfs(0, 13);
	std::cout << ans;

	return 0;
}

方法二：step代表目前手中的卡牌点数，cnt代表目前手中的卡牌张数，当手中有13张卡牌时停止递归,方案数+1。当目前手中卡牌点数超过13时或者手中卡牌数超过13时也剪掉，但不加方案数。

# include <iostream>

typedef long long ll;

ll ans = 0;

void dfs(int step, int cnt) {
   
	if (cnt == 13) {
   
		++ans;
		return;
	}
	
	if (step >= 13 || cnt >= 13) {
   
		return;
	}
	
	for (int i = 0; i <= 4; i++) {
   
		dfs(step + 1, cnt + i);
	}
}

int main() {
   
	dfs(0, 0);
	std::cout << ans;		
    
	return 0;
}

运行结果：

先将所有的钞票张数减一，sum总和减18，再进行DFS。

其余部分和例3差不多。

# include <iostream>
# include <set>
# include <tuple>

int money[5] = {
   0, 1, 2, 5, 10};
int arr[107];
int cnt[15];

typedef std::tuple<int, int, int, int> P;

std::set<P> st;

void dfs(int sum, int choose) {
   
	if (sum == 100 - 1 - 2 - 5 - 10) {
   
		P t = std::make_tuple(cnt[1] + 1, cnt[2] + 1, cnt[5] + 1, cnt[10] + 1);
		st.insert(t);

		return ;
	} else if (sum > 100 - 1 - 2 - 5 - 10) {
   
		return;
	} else {
   
		for (int i = choose; i >= 1; i--) {
   
			cnt[money[i]]++;
			dfs(sum + money[i], i);
			cnt[money[i]]--;
		}
	}
}

int main() {
   
	dfs(0, 4);

	std::cout << st.size() << "\n";
	for (auto it = st.begin(); it != st.end(); it++) {
   
		std::cout << std::get<0>(*it) << " ";
		std::cout << std::get<1>(*it) << " ";
		std::cout << std::get<2>(*it) << " ";
		std::cout << std::get<3>(*it) << "\n";
	}

	return 0;
}

# include <iostream>
# include <set>
# include <tuple>

int money[5] = {
   1, 2, 5, 10};
int cnt[15];

typedef std::tuple<int, int, int, int> P;

std::set<P> st;

void dfs(int step, int sum) {
   
	if (sum == 100 - 1 - 2 - 5 - 10) {
   
		P t = std::make_tuple(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, cnt[3] + 1);
		st.insert(t);

		return;
	}

	if (step >= 4) {
   
		return;
	}

	for (int i = 0; i <= 100; i++) {
   
		cnt[step] += i;
		if (sum + money[step] * i <= 100 - 1 - 2 - 5 - 10) {
   
			dfs(step + 1, sum + money[step] * i);
		} else {
   
			cnt[step] -= i;
			break;
		}
		cnt[step] -= i;
	}
}

int main() {
   
	dfs(0, 0);

	std::cout << st.size() << "\n";
	for (auto it = st.begin(); it != st.end(); it++) {
   
		std::cout << std::get<0>(*it) << " ";
		std::cout << std::get<1>(*it) << " ";
		std::cout << std::get<2>(*it) << " ";
		std::cout << std::get<3>(*it) << "\n";
	}

	return 0;
}

4. 递归实现指数型枚举

从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
方法1：二进制状态压缩

/************************** https://www.acwing.com/problem/content/94/ Time 33 ms Memory 860 KB ***************************/
# include <iostream>
# include <cstdio>

int n;

void print(int num) {
   
	for (int i = 0; i < n; i++) {
   
		if ((num >> i) & 1) {
   
			std::cout << i + 1 << " ";
		}
	}
}

int main() {
   
	std::cin >> n;
	
	for (int i = 0; i < 1 << n; i++) {
   
		print(i);
		puts("");
	}

	return 0;
}

方法2：DFS

/************************** https://www.acwing.com/problem/content/description/94/ Time 32 ms Memory 852 KB **************************/
# include <iostream>
# include <vector>

int n;
std::vector<int> chosen;

void print() {
   
	for (int i = 0; i < chosen.size(); i++) {
   
		std::cout << chosen[i] << " ";
	}
	puts("");
}

void dfs(int step) {
   
	if (step == n + 1) {
   
		print();

		return;
	}
	
	dfs(step + 1);
	
	chosen.push_back(step);
	dfs(step + 1);
	
	chosen.pop_back(); 
} 

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

5. 递归实现组合型枚举

和递归实现指数型枚举的思路差不多，只不过多了剪枝和排序的步骤。
当chosen数组大小大于m或者接下来的递归即使所有的数全部选上也不能达到m个时终止递归。
打印的数字需要进行排列，可以将chosen数组放入一个vecotor中，dfs完成后先进行排序，再进行输出。由于vector的比较大小默认时按照字典序来排的，所以可以直接调用STL中的sort函数。

/************************** https://www.acwing.com/problem/content/description/95/ Time 147 ms Memory 2448 KB **************************/
# include <iostream>
# include <vector>
# include <algorithm>

int n;
int m;
std::vector<int> chosen;
std::vector<std::vector<int>> save;

void fsave() {
   
	save.push_back(chosen);
}

void print() {
   
	std::sort(save.begin(), save.end());
	for (int i = 0; i < save.size(); i++) {
   
		for (int j = 0; j < save[i].size(); j++) {
   
			std::cout << save[i][j] << " ";
		}
		puts("");
	}
}

void dfs(int step) {
   
	if (chosen.size() > m || chosen.size() + (n - step + 1) < m) {
   
		return;
	}
	
	if (step == n + 1) {
   
		fsave();

		return;
	}
	
	dfs(step + 1);
	
	chosen.push_back(step);
	dfs(step + 1);
	
	chosen.pop_back(); 
} 

int main() {
   
	std::cin >> n >> m;
	dfs(1);
	print();
	
	return 0;
}

6.[蓝桥杯2016决赛]凑平方数

# include <iostream>
# include <cmath>
# include <algorithm>
# include <set>
# include <vector>

typedef long long ll;

const double eps = 1e-8;
int arr[10] = {
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<ll> nums(10, 0);

std::set<std::vector<ll> > res;

bool isqnum(long long num) {
   
	double d = sqrt(num);
	return fabs(d - (ll)d) <= eps;
}

void dfs(int i, int n) {
   
	if (i == 10) {
   
		std::vector<ll> vt(10, 0);
		std::copy(nums.begin(), nums.begin() + n, vt.begin());
		sort(vt.begin(), vt.end());

		res.insert(vt);
		return ;
	}

	if(arr[i] == 0) {
   
		nums[n] = 0;
		dfs(i + 1, n + 1);
		return;
	}

	ll num = 0;
	for(int j = i; j < 10; ++ j) {
   
		num = num * 10 + arr[j];
		if (isqnum(num)) {
   
			nums[n] = num;
			dfs(j + 1, n + 1);
		}
	}
}

int main() {
   
	do {
   
		dfs(0, 0);
	} while(std::next_permutation(arr, arr + 10));

	std::cout << res.size();

	return 0;
}