HDU 1181 变形课 深度优先搜索(DFS)简单题

题意：给出很多个字符串，每个串表示该串的首字母代表的物体能转变成尾字母代表的物体，问的是'b'物体能不能转变成'm'物体．

思路：先找出所有以'b'为首字母的串，它们都作为起点，一直很后搜索(连接)，看能否找到'm'

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include

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 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 if(st[i]!='b')continue;
vis[i]=1;
DFS(i);
}
if(ok)puts("Yes.");
else puts("No.");
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include

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 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 if(st[i]!='b')continue;
vis[i]=1;
DFS(i);
}
if(ok)puts("Yes.");
else puts("No.");
}
return 0;
}