校oj 第二届程序设计大赛 Harry的魔法课

题目链接

需要连接校园网

Description

魔法课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的，但是他发现了变形咒语的一个统一规律：如果咒语是以字母a开头字母b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表，想让你帮忙计算一下他是否能完成老师的作业，将一个B(ball)变成一个M(mouse)。你知道，如果他自己不能完成的话，他就只好向Hermione请教，并且被迫听一大堆好好学习的道理。

Input

测试数据有多组。每组有N行(1 <= N <= 10)，每行一个单词，仅包括小写字母，是Harry所会的所有咒语。数字0表示一组输入结束.

Output

如果Harry可以完成他的作业,就输出Yes,否则就输出No

Sample Input

so
soon
river
goes
them
got
moon
begin
big
0

Sample Output

Yes

Hint

【提示】：Harry 可以念这个咒语:"big-got-them"，从而将ball变成mouse

思路

看题目意思应该是要用搜索big-got-them可以将ball变成mouse，big-goo-oil-liom 也可以将ball变成mouse，直接上代码

代码

#include 
#include 

using namespace std;

string world[11], res[11], ree[11];
int cnt, cnt1, cnt2, flag;

void dfs(string start, string end){  
	// 如果前一个单词的最后一个字母等于后一个单词的第一个字母表示可以找到 
	if(start[start.length()-1] == end[0]){
		flag = 1;
		return;
	}
	for(int i = 0; i < cnt; i++){
		// 在所以单词中搜索是否存在有一个单词的第一个字母等于start的最后一个字母 
		if(start[start.length()-1] == world[i][0]) 
			dfs(world[i], end); // 更新start 
		// 在所以单词中搜索是否存在有一个单词的最后一个字母等于end的第一个字母
		if(end[0] == world[i][world[i].length()-1])
			dfs(start, world[i]); // 更新end 
	}	
}

int main(){
	string str;
	while(cin>>str){
		if(str[0] == '0'){ // 一组数据输入完成 
			// 枚举所有组合 
			for(int i = 0; i < cnt1; i++) 
				for(int j = 0; j < cnt2; j++){
					dfs(res[i], ree[j]);
				}
			if(flag)
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
			cnt = 0;
			cnt1 = 0;
			cnt2 = 0;
			flag = 0;
		}
		world[cnt] = str;
		// 在所有单词中找到第一个字母为'b'的单词并保存
		if(world[cnt][0] == 'b')  
			res[cnt1++] = world[cnt];
		 // 在所有单词中找到最后一个字母为'm'的单词并保存
		else if(world[cnt][world[cnt].length()-1] == 'm')
			ree[cnt2++] = world[cnt];
		cnt++;
	}
}