编程题的100种错法——单词接龙

【题目描述】

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

【输入描述】

输入的第一行为一个单独的整数n(n≤20)表示单词数，以下n行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

【输出描述】

只需输出以此字母开头的最长的“龙”的长度。

【样例输入】

5
at
touch
cheat
choose
tact
a

【样例输出】

23

【错误解法1】—贡献者：贤同学

#include<bits/stdc++.h>
using namespace std;
int fg[1000];//起始接龙单词长度
char c[1000][30];//存放所有单词
int main() {
	int n,flag[1000]= {0}/*是否为可起始单词*/;
	cin>>n;
	char a,x[30];
	for(int i=0; i<n; i++) {
		cin>>x;
		for(int j=0; j<strlen(x); j++) {
			c[i][j]=x[j];//用x作为转换将单词读入到从数组中
		}
		fg[i]=strlen(x);
	}
	for(int i=0; i<n; i++) {
		for(int j=0; j<30; j++) {
			cout<<c[i][j];
		}
                cout<<endl;
	}
	char f;
	cin>>f;/*输入*/
	int j=1;
	for(int i=0; i<n; i++) {
		if(c[i][0]==f) {
			flag[j]=i+1;
			j++;
		}
	}//找出可起始单词
	int f1=1,max=0;
	while(flag[f1]!=0) {
		int sum2=fg[f1];
		for(int i=1; i<fg[flag[f1]]; i++) { //每个单词一个一个字母找
			if(i==f1)continue;//如果碰到自己就跳过
			for(int j=0; j<n; j++) {
				if(c[j][0]!=c[flag[f1]][i]) {
					continue;
				}//如果不是就跳过
				else {
					sum2+=(fg[j]-fg[i]-i-1);
				}//反之则加长度
			}
		}
		if(sum2>max) {
			max=sum2;
		}//更新最长长度
		f1++;
	}
	cout<<max;//输出
	return 0;
}

返回目录：编程题的100种错法