hdu1181 dfs搜索之变形课
搜索 DFS 变形
2023-09-11 14:20:45 时间
原题地址
这道题数据据说比較水,除了第一组数据是Yes以外。其余都是No。非常多人抓住这点就水过了。当然了,我认为那样过了也没什么意思。刷oj刷的是质量不是数量。
这道题从题目上来看是个不错的 搜索题,解法多种多样,有 dfs。bfs,并查集,dijkstra算法都能解决。
题目分析:
题目中给了非常多字符串。可是关心的仅仅是字符串的第一个和最后一个字符。咋看起来。貌似是要建立一个个字符间的“映射”,事实上不然,这事实上能够转化为一张26*26的有向图。
有最多26个结点,原先的字符间映射关系就转化为结点之间有路径。问题就变成了能否找一条路径从结点b到结点m。
我用的dfs解的。
#include<iostream> #include<cstring> using namespace std; bool g[26][26];//全局变量声明时会被初始化为0(false) bool used[26];//全局变量声明时会被初始化为0(false) bool dfs(int i) { used[1]=true; for(int j=0;j<26;j++) { if(i!=j&&!used[j]&&g[i][j]) { if(i!=1) g[1][j]=true; used[j]=true; dfs(j); } } return g[1][12];//b为1,m为12 } int main() { char s[100]; while(cin>>s) { if(s[0]!='0') { int len=strlen(s); g[s[0]-'a'][s[len-1]-'a']=true; continue; } if(dfs(1)) cout<<"Yes."<<endl; else cout<<"No."<<endl; memset(g,false,sizeof(g)); memset(used,false,sizeof(used)); } }
相关文章
- 地牢逃脱----DFS搜索最优解
- Java实现 LeetCode 813 最大平均值和的分组 (DFS+DP记忆化搜索)
- java实现第六届蓝桥杯密文搜索
- scrapy+pyppeteer指定搜索动态爬取头条
- mysql 必知必会整理—组合查询与全文搜索[九]
- 文章--笔记本蓝牙可以搜索到手机,但是怎么连接不了?
- scrapy+pyppeteer指定搜索动态爬取头条
- SAP CRM IBASE对应的搜索实现,动态SQL语句的拼装
- Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS,最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)
- Android 11.0 12.0Settings 搜索功能屏蔽某个app
- openpose_net随机搜索(维度搜索)网络源代码
- [poj 2331] Water pipe ID A*迭代加深搜索(dfs)
- 1038. 从二叉搜索树到更大和树-dfs方法
- CoreJava_线程并发(堵塞队列):在某个目录下搜索含有某keyword的文件
- dfs 解决(隐式)图搜索问题
- dfs 解决八皇后问题 以及其他图搜索问题