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; }

运行结果：3598180

如果需要考虑花色呢？那就将卡牌数加上权值，w[0] = 1, w[1] = 4, w[2] = 6, w[3] = 4, w[4] = 1, 在DFS时保存路径，在递归结束时方案数加上该路径的权值的乘积。

4. 找零钱

将一张100元的钞票换成1元、2元、5元和10元的零钱，每种零钞至少一张，编写程序输出所有的换法。 第一行输出换算的方案数T，接下来T行每行4个数字a，b，c，d分别代表1元的张数、2元的张数、5元的张数、10元的张数。按照字典序从小到大输出。

先将所有的钞票张数减一，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; }