美文网首页NOIP之路
单词接龙 DFS 洛谷P1019

单词接龙 DFS 洛谷P1019

作者: 静_谷 | 来源:发表于2018-06-11 14:54 被阅读8次

    主要是字符串拼接处理比较麻烦(下见mix函数),DFS还是比较简单的

    鉴定

    读题有坑 注意max_初始化

    短小精悍(?)的深搜代码:

    #include <iostream>
    #include <string>
    using namespace std;
    int n,max_;
    string str[20];
    int b[20];
    int mix(string str1, string str2) {//如果没有重叠部分就返回-1,否则返回重叠部分开始的位置
        for(int k=str1.size()-1; k>=0; k--) {//贪心,为了让合并后的字符串尽量长一定要从后往前判断
            bool r=1;
            int i_2=0;
            for(int i=k; i<=str1.size()-1; i++) {
                if(!(i_2<=str2.size()-1)) {//判断str2边界
                    r=0;
                    break;
                } else if(str1[i]!=str2[i_2]) {
                    r=0;
                    break;
                }
                i_2++;
            }
            if(r) return k;
        }
        return -1;
    }
    void search(int cur, string s) {
        bool bb=1;//bb规定:0表示有至少一个解,1表示此情况无解
        for(int i=0; i<n; i++)
            if(b[i]<=1) {//注意每个单词可以用两次
                bb=0;
                int t=mix(s,str[i]);
                if(t!=-1) {
                    string news;
                    for(int i=0; i<=t-1; i++)
                        news+=s[i];
                    news+=str[i];//合并两个字符串
                    b[i]+=1;
                    search(cur+1, news);
                    b[i]-=1;
                }
            }
        if(bb&&max_<s.size())
            max_=s.size();//更新max_
    }
    int main() {
        ios::sync_with_stdio(false);//cin cout速度嗖嗖嗖
        cin>>n;
        for(int i=0; i<=n-1; i++)
            cin>>str[i];
        char a;
        cin>>a;
        for(int i=0; i<n; i++)
            if(str[i][0]==a) {//枚举每个以字符a开头的字符串
                b[i]=1;
                string t=str[i];
                if(max_<t.size()) {
                    max_=t.size();//初始化max_
                }
                search(0, t);//开搜!
                b[i]=0;
            }
        cout<<max_;
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:单词接龙 DFS 洛谷P1019

        本文链接:https://www.haomeiwen.com/subject/iakheftx.html