首页 > 代码库 > hdu1181 bfs搜索之变形课
hdu1181 bfs搜索之变形课
原题地址
这道题数据据说比较水,除了第一组数据是Yes以外,其余都是No,很多人抓住这点就水过了。当然了,我觉得那样过了也没什么意思。刷oj刷的是质量不是数量。这道题从题目上来看是个不错的 搜索题,解法多种多样,有 dfs,bfs,并查集,dijkstra算法都能解决。
题目分析:
题目中给了很多字符串,但是关心的只是字符串的第一个和最后一个字符。咋看起来,貌似是要建立一个个字符间的“映射”,其实不然,这其实可以转化为一张26*26的有向图。有最多26个结点,原先的字符间映射关系就转化为结点之间有路径。问题就变成了是否能找一条路径从结点b到结点m。
我用的bfs解的。
#include<iostream> #include<cstring> using namespace std; bool g[26][26];//全局变量声明时会被初始化为0(false) bool used[26];//全局变量声明时会被初始化为0(false) bool bfs(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; bfs(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(bfs(1)) cout<<"Yes."<<endl; else cout<<"No."<<endl; memset(g,false,sizeof(g)); memset(used,false,sizeof(used)); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。