当前位置: 首页 > news >正文

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

http://www.lryc.cn/news/148003.html

相关文章:

  • Seaborn数据可视化(四)
  • kubernetes deploy standalone mysql demo
  • 【Map】Map集合有序与无序测试案例:HashMap,TreeMap,LinkedHashMap(121)
  • TiDB Serverless Branching:通过数据库分支简化应用开发流程
  • 运用亚马逊云科技Amazon Kendra,快速部署企业智能搜索应用
  • C# 使用 OleDbConnection 连接读取Excel的方法
  • 【LeetCode-中等题】98. 验证二叉搜索树
  • Leetcode-每日一题【剑指 Offer 37. 序列化二叉树】
  • 删除无点击数据offer数据分析使用
  • 【Apollo学习笔记】——规划模块TASK之SPEED_BOUNDS_PRIORI_DECIDER
  • 物理机ping不通windows server 2012
  • 誉天HCIE-Datacom丨为什么选择誉天数通HCIE课程学习
  • Python文本终端GUI框架详解
  • 01_lwip_raw_udp_test
  • 学习ts(十一)本地存储与发布订阅模式
  • MySQL对NULL值处理
  • Vector 动态数组(迭代器)
  • 多组背包恰好装满方案数
  • Oracle查询语句中做日期加减运算
  • Unity贝塞尔曲线的落地应用-驱动飞行特效
  • VTK——设置交互样式上的鼠标回调函数
  • Flutter实现动画列表AnimateListView
  • 【LeetCode-中等题】236. 二叉树的最近公共祖先
  • 如何拼接两个视频在一起?
  • Programming abstractions in C阅读笔记:p130-p131
  • 如何在Windows本地快速搭建SFTP文件服务器,并通过端口映射实现公网远程访问
  • C#---第二十:不同类型方法的执行顺序(new / virtual / common / override)
  • lnmp架构-PHP
  • 【javascript实操记录】
  • Mysql--技术文档--悲观锁、乐观锁-《控制并发机制简单认知、深度理解》