Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=1181
看完这题首先想到的是用DFS，因为只要找到就行了，不求找到的最快方法。首先从开头字母为'b'的单词出发，目标为首尾相接，且末字母为'm'的单词。中间的搜索时的下一个链接单位自然是首尾相接的单词。
DFS:
#include#include #include #include using namespace std;const int maxn = 1000 + 24;string word[maxn];bool vis[maxn];int pos;int flag=0;void dfs( string str ){ if( flag ) return ; int i; for( i=0;i<=pos;i++ ) if( !vis[i] ) { if( word[i][0] == str[ str.length()-1 ] && word[i][ word[i].length()-1 ]=='m' ) //满足首尾相连又已'm'结尾 flag=1; else if( word[i][0]==str[ str.length()-1 ] ) //满足首尾相连的情况 { vis[i]=true; dfs( word[i] ); vis[i]=false; } }}int main(){ pos=0; int i,j; memset( vis,false,sizeof(vis) ); while( cin>>word[pos] ) { if( word[pos][0]=='0' ) //以输入'0'为结尾 { flag=0; for( i=0;i<=pos;i++ ) { if( word[i][0]=='b' ) { vis[i]=true; dfs( word[i] ); vis[i]=false; } } if( flag ) cout<<"Yes.\n"; else cout<<"No.\n"; pos=0; memset( vis,false,sizeof(vis) ); //重新初始化 } else pos++; //没有结尾就一直输入下一个 } return 0;}
但当我AC后，稍微一思考，发现可以优化。因为我不需要关注你输入的单词的每一个字母，我所要知道的仅仅为每个输入单词的首字母与末字母。那么我可以建一个链接矩阵，表示两个字母间的链接关系。当然这个连接是单向的，比如输入big，'b'可以指向'g'，而不是'g'指向'b'。
此处用了BFS:
#include#include #include #include #include using namespace std;const int maxn = 30;bool word[maxn][maxn]; //链接矩阵bool vis[maxn][maxn]; //是否已访问bool bfs(){ const int start = 'b'-'a'; const int finish = 'm'-'a'; queue qt; qt.push( start ); //从'b'出发 int t, i; while( !qt.empty() ) { t = qt.front(); qt.pop(); if( word[t][finish] ) //找到末尾是'm'的单词 return true; for( i=0;i<='z'-'a';i++ ) if( !vis[t][i] && word[t][i] ) //寻找未访问的首尾组合 { vis[t][i] = true; qt.push(i); } } return false;}int main(){ string temp; memset( vis, false, sizeof(vis) ); memset( word, false, sizeof(word) ); while( cin>>temp ) { if( temp[0]=='0' ) //一组输入完毕 { if( bfs() ) cout<<"Yes.\n"; else cout<<"No.\n"; memset( vis, false, sizeof(vis) ); memset( word, false, sizeof(word) ); } else word[ temp[0]-'a' ][ temp[ temp.length()-1 ]-'a' ] = true; } return 0;}
除了BFS，DFS，还可以用最短路径，判断起点'b'能否到'm'即可，这里就不贴代码了。网上也还有很多的其他解法。
总之，这道题不难，但对扩展思路还是有一定帮助的。