(以“ 分类:深度优先搜索分类:广度优先搜索 ==摘要== {{信息题|字符变换|http://www.codevs.cn/problem/1099/|1|80|超时|time=2014/12/23 21:38:...”为内容创建页面)
 
(参数)
第1行: 第1行:
 
 
[[分类:深度优先搜索]][[分类:广度优先搜索]]
 
[[分类:深度优先搜索]][[分类:广度优先搜索]]
 
==摘要==
 
==摘要==
{{信息题|字符变换|http://www.codevs.cn/problem/1099/|1|80|超时|time=2014/12/23 21:38:37}}
+
{{信息题|字符变换|http://www.codevs.cn/problem/1099/|1|100|80|超时|time=2014/12/23 21:38:37}}
 
==题意==
 
==题意==
 
一串字符,替换成另一串字符,问最小步数(给字典)。
 
一串字符,替换成另一串字符,问最小步数(给字典)。
第63行: 第62行:
 
     return 0;
 
     return 0;
 
}
 
}
 +
 
</pre>
 
</pre>
 
|code1099}}
 
|code1099}}
第115行: 第115行:
 
     if(f==t)
 
     if(f==t)
 
         return 1;
 
         return 1;
 +
 
     for(int i=1;i<=n;++i)
 
     for(int i=1;i<=n;++i)
 
     {
 
     {
第156行: 第157行:
 
     return 0;
 
     return 0;
 
}
 
}
 +
 
|code1099s}}
 
|code1099s}}

2014年12月23日 (二) 21:48的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
字符变换 ★☆☆☆☆ 答案正确 100 2014/12/23 21:38:37 80(超时)

题意

一串字符,替换成另一串字符,问最小步数(给字典)。

题解

  • 迭代加深搜索(懒得写广搜,这样真的好吗……),没什么特别的
  • 然后写完就发现T了
  • 优化就是改成双向搜索,由于是指数型增长,这样可以提升效率非常多。

代码

1099朴素迭代加深(80分).cpp代码已折叠
展开折叠内容
#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;
}

1099双向迭代加深.cpp
展开折叠内容
code1099s

著作权声明[编辑]

关于[编辑]