rainman's blog

学海无涯,回头是岸

题解 P1019 【单词接龙】

算法分析

  1. 如果给你一个单词,按照题意,你就需要以这个单词的最后一个字母(或是最后两个字母...直到除了首字母以外(因为不能有包含关系)的所有字母)开始寻找下一个单词,同时记下不重合的长度。

  2. 我们不难发现,其实这个过程是一个自相似的过程,所以我们考虑使用递归,也就是DFS算法。

  3. 怎么记录目前字符串的长度呢?你当然可以使用全局变量,但是由于DFS需要回溯,这样不大方便。我们可以玄学地在DFS里加上参数(int)now_len表示当前长度,调用的时候加以修改就可以了。

  4. 那么选了一个单词之后,以什么开头寻找下一个呢?由 1 的分析可知,我们要在一个循环体里面递归调用DFS——我们在DFS里设置另一个参数(string)s来表示寻找的依据。

数据结构

  • 声明bool vis[21][2]; 如果一个单词被用过一次,vis[i][0]的值为true;如果使用了两次,vis[i][1]变为true。

下面给出代码:

#include<bits/stdc++.h>
using namespace std;
string word[21],start;
bool vis[21][2];
int n,dragon_len;
void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      cin>>word[i];
    cin>>start;//开始的字符 
}
void dfs(int now_len,string s)
{
    int s_len=s.size();// s的大小以后会经常用到,提前计算提高速度 
    bool flag=false;
    for(int i=1;i<=n;i++)
    {
        //如果这个单词已经被用完了,直接跳过 
        if(vis[i][1]==true)continue; 
        bool ok=true;
        for(int j=0;j<s_len;j++)
        {
            if(word[i][j]!=s[j])
            {
                ok=false; break;
            }
        }
        if(ok)
        {
            flag=true;
            bool OK=false;
            if(vis[i][0])vis[i][1]=true;
            else 
            {
                vis[i][0]=true;
                OK=true;
            }
            int word_len=word[i].size();
            for(int k=1;k<=word_len-1;k++)
            {
                dfs(now_len+word_len-s_len,word[i].substr(k,word_len-k));
            }
            vis[i][1]=false;
            if(OK)vis[i][0]=false;
        }        
    }
    if(flag==false)
    {
        if(now_len>dragon_len)
        dragon_len=now_len;
        return;
    }
}
int main()
{
    input();
    dfs(1,start);//第一个字符长度已经为1 
    cout<<dragon_len;
    return 0;
}

一些值得注意的细节

  1. 不知道substr()函数?点击这里

  2. 语句bool flag=false;是理解该程序的一个关键,就是它决定了递归的边界。在if(ok)语段中,我们不难发现,如果已经没有单词可以继续接龙了,if不会执行,也就是说,flag用来判断它是否执行----如果没有则到达边界return。


2018-01-01 10:47:58 in 题解