单词接龙（DFS）2017.3.10

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。 Input  有多测测试数据。 对于每组测试数据，第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在. Output 只需输出以此字母开头的最长的“龙”的长度 Sample Input 5 at touch cheat choose tact a Sample Output 23 Hint 样例中连成的“龙”atoucheatactactouchoose。 来自胖头鱼的分析：首先判断这是一个dfs，问题难点就在每一个单词可以使用两次（且单词与单词之间不能存在包含关系）。如果有ababa和abababc这样的单词，最好的连接办法就是只重叠一个a，这样最好是采用前面单词往前跑，后面单词往后跑的解决办法。用一个二维数组（图） 来存每两个单词的重叠部分长度。剩下的开一个数组记录单词使用频次就可以开始搜索了。 AC代码： #include<iostream> #include<string> #include<iomanip> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; string str[21]; int n; int map[21][21]; int vis[21]; int ans = 0; int check(int x, int y) {  int first, last;  int p = str[x].length();  int q = str[y].length();  for (int j = str[x].length() - 1;j >0;j--)  {   if (str[y].at(0) == str[x].at(j))   {    bool flag = 1;    for (int k = j;k < p&&k - j < q;k++)    {     if (str[x].at(k) != str[y].at(k - j))     {      flag = 0;break;     }    }    if (flag&&p - j < q)  return p-j;   }  }  return 0; } void dfs(int x, int num) {   if (num > ans) ans = num;  for (int o = 1;o <= n;o++)  {   if (map[x][o] && vis[o] < 2)   {        vis[o]++;    num+= str[o].length()-map[x][o];           dfs(o, num);    vis[o]--;    num -= str[o].length() - map[x][o];   }    }   return; } int main() {  while (cin >> n)  {   ans = 0;   memset(map,0, sizeof(map));   memset(vis,0, sizeof(vis));   for (int i = 1;i <= n;i++)   {    cin >> str[i];   }   cin >> str[0];   for (int i = 0;i <= n;i++)   {    for (int p = 0;p <= n;p++)    {     map[i][p] = check(i, p);    }   }   for (int i = 1;i <= n;i++)   {    if (str[0].at(0) == str[i].at(0))    {           vis[i] = 1;       dfs(i, str[i].length());     memset(vis, 0, sizeof(vis));    }   }     cout << ans << endl;  }  return 0; }