查看CodeVS/1099的源代码 ←CodeVS/1099

[[分类:深度优先搜索]][[分类:广度优先搜索]]
==摘要==
{{信息题|字符变换|http://www.codevs.cn/problem/1099/|1|100|80|超时|time=2014/12/23 21:38:37}}
==题意==
一串字符，替换成另一串字符，问最小步数（给字典）。
==题解==
*迭代加深搜索（懒得写广搜，这样真的好吗……），没什么特别的
*然后写完就发现T了
*优化就是改成双向搜索，由于是指数型增长，这样可以提升效率非常多。
==代码==
{{折叠|1099朴素迭代加深(80分).cpp代码已折叠
|<pre>
#include<iostream>
#include<string>
using namespace std;
string f,t,df[10],dt[10];
int n,depth;
void init();
const bool work (const int&);
const bool dfs(const string & f,const int &depth);
int main()
{
    init();
    for(int i=1;i<=10;++i)//deeper the depth step by step
    {
        if(work(i))
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"NO ANSWER!"<<endl;
    return 0;
}
void init()
{
    cin>>f>>t;
    for(n=1;cin>>df[n]>>dt[n];++n);
    --n;
}
const bool work(const int &depth)
{
    ::depth=depth;
    return dfs(f,0);
}
const bool dfs(const string & f,const int &depth)
{
    if(depth>::depth)
        return 0;
    if(f==t)
        return 1;
    for(int i=1;i<=n;++i)
    {
        int pos=f.find(df[i]);
        if(pos==string::npos)
            continue;
        string nt=f;
        nt.replace(pos,df[i].size(),dt[i]);
        if(dfs(nt,depth+1))
            return 1;
    }
    return 0;
}

</pre>
|code1099}}
{{折叠|1099双向迭代加深.cpp|
#include<iostream>
#include<iterator>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
string f,t,df[10],dt[10];
int n,depth;
void init();
const bool work ();
const bool dfs(const string & f,const int &depth);
const bool rwork();
const bool rdfs(const string & f,const int &depth);
map<string,int> us;
int main()
{
    init();
    if(work())
    {
        cout<<us[t];
    }
    else if(rwork())
    {
        cout<<depth+5;
    }else
        cout<<"NO ANSWER!"<<endl;
    return 0;
}
void init()
{
    cin>>f>>t;
    for(n=1;cin>>df[n]>>dt[n];++n);
    --n;
}
const bool work()
{
    ::depth=5;
    return dfs(f,0);
}
const bool dfs(const string & f,const int &depth)
{
    if(depth>::depth)
        return 0;
    if(us.count(f))
        us[f]=min(us[f],depth);
    else
        us[f]=depth;
    if(f==t)
        return 1;

    for(int i=1;i<=n;++i)
    {
        int pos=f.find(df[i]);
        while(pos!=string::npos)
        {
            string nt=f;
            nt.replace(pos,df[i].size(),dt[i]);
            if(dfs(nt,depth+1))
                return 1;
            pos=f.find(df[i],pos+1);
        }
    }
    return 0;
}
const bool rwork()
{
    for(depth=1;depth<=5;++depth)
        if(rdfs(t,0))
            return 1;
    return 0;
}
const bool rdfs(const string & f,const int &depth)
{
     if(depth>::depth)
        return 0;
    if(us.count(f))
        return 1;
    for(int i=1;i<=n;++i)
    {
        int pos=f.find(dt[i]);
        while(pos!=string::npos)
        {
            string nt=f;
            nt.replace(pos,dt[i].size(),df[i]);
            if(rdfs(nt,depth+1))
                return 1;
            pos=f.find(dt[i],pos+1);
        }
    }
    return 0;
}

|code1099s}}