博客

http://acm.hdu.edu.cn/showproblem.php?pid=1181

题意：

给出很多个字符

串，

每个串

表示该串的首字母代表的物体能转变成尾

字母代

表的物体，问

的是’b’物体能不能转变成’m’物体．

思路

：先找出所有

以’b’

为首字母的串，它们都作为起点，一直很后搜索

(连接)，看能否找到’m’

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<queue>

using namespace std;
const int maxn=100000;

char st[maxn],et[maxn];
int vis[maxn],t;
bool ok;

void DFS(int x){
    if(et[x]=='m'){
        ok=true; return;
    }
    for(int i=0;i<t;++i){
        if(vis[i]||st[i]!=et[x])continue;
        vis[i]=1;
        DFS(i);
        vis[i]=0;
        if(ok)return;
    }
}

int main() {
    string s;
    while(cin>>s){
        t=0;
        while(s[0]!='0'){
            st[t]=s[0];
            et[t++]=s[s.size()-1];
            cin>>s;
        }
        memset(vis,0,sizeof(vis));
        ok=false;
        for(int i=0;i<t;++i){
            if(st[i]!='b')continue;
            vis[i]=1;
            DFS(i);
        }
        if(ok)puts("Yes.");
        else puts("No.");
    }
    return 0;
}