（以“ 分类:深度优先搜索分类:广度优先搜索 ==摘要== {{信息题|字符变换|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}} | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 字符变换 | ★☆☆☆☆ | 答案正确 | 100 | 2014/12/23 21:38:37 | 80（超时） |
一串字符，替换成另一串字符，问最小步数（给字典）。
| 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
|
CloudLunar