三道dfs题

一：1114. 棋盘问题 - AcWing题库

分别枚举行和列，能填的地方就填，dfs就行

#include <iostream>
using namespace std;const int N = 10;
char g[N][N];
int n, k;
int res;
bool st[N];void dfs(int u, int cnt) // u枚举行
{if(cnt == k ) {res ++;return;}if(u >= n) return;for(int i = 0; i < n; i ++ ) // 这里枚举列{if(g[u][i] == '#' && !st[i]) {st[i] = true;dfs(u + 1, cnt + 1);st[i] = false;}}dfs(u + 1, cnt); // 回溯
}int main()
{while(scanf("%d%d", &n, &k)){if(n == -1 && k == -1) break;res = 0;for(int i = 0; i < n; i ++ ){cin >> g[i];}dfs(0, 0);cout << res << endl;}return 0;
}

二：P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题类似于组合型枚举

直接

#include <iostream>
using namespace std;int n, k;
int res; 
int last;void dfs(int u, int start, int sum)
{if(sum > n) return ;if(u > k){if(sum == n){res ++;}return ;}for(int i = start; i <= n && sum + i * (k - u + 1) <= n; i ++ ) // 组合型枚举的做法就是用start去规定下一个位置{dfs(u + 1, i, sum + i);}
}int main()
{cin >> n >> k;dfs(1, 1, 0);cout << res;return 0;
}

三：P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题最主要的就是dfs前的预处理

1是将重合部分的长度处理出来，2是怎么记录每个单词最多用两次

#include <iostream>
#include <string>
using namespace std;int n;
string s[20];
int m[20][20], used[20], ans; // m表示i与j重合的长度, used 表示i用过的次数
char start;void dfs(string dragon, int pos)
{ans = max(ans, (int)dragon.size()); // 这里必须类型一致used[pos] ++;for(int i = 0; i < n; i ++ ){if(m[pos][i] && used[i] < 2){dfs(dragon + s[i].substr(m[pos][i]), i); // 接龙}}// 回溯 used[pos] --;
}int main()
{cin >> n;for(int i = 0; i < n; i ++ ){cin >> s[i];}cin >> start;// 预处理一下，填mfor(int i = 0; i < n; i ++ ){for(int j = 0; j < n; j ++ ){string a = s[i], b = s[j];for(int k = 1; k < a.size() && k < b.size(); k ++ ){if(a.substr(a.size() - k, k) == b.substr(0, k)){m[i][j] = k;break; // 重合长度最小时，答案最大}}}}for(int i = 0; i < n; i ++ ){if(s[i][0] == start){dfs(s[i], i);}}cout << ans;return 0;
}