（以“ 分类:深度优先搜索分类:广度优先搜索 ==摘要== {{信息题|字符变换|http://www.codevs.cn/problem/1099/|1|80|超时|time=2014/12/23 21:38:...”为内容创建页面） |
小 （修复pre） |
||
| （未显示1个用户的1个中间版本） | |||
| 第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}} |
==题意== | ==题意== | ||
一串字符，替换成另一串字符，问最小步数（给字典）。 | 一串字符，替换成另一串字符，问最小步数（给字典）。 | ||
| 第10行： | 第9行： | ||
*优化就是改成双向搜索，由于是指数型增长，这样可以提升效率非常多。 | *优化就是改成双向搜索，由于是指数型增长，这样可以提升效率非常多。 | ||
==代码== | ==代码== | ||
| − | {{折叠|1099朴素迭代加深(80分).cpp代码已折叠 | + | {{折叠|1099朴素迭代加深(80分).cpp代码已折叠|<pre> |
| − | |<pre> | + | |
#include<iostream> | #include<iostream> | ||
#include<string> | #include<string> | ||
| 第63行： | 第61行： | ||
return 0; | return 0; | ||
} | } | ||
| + | |||
</pre> | </pre> | ||
|code1099}} | |code1099}} | ||
| − | {{折叠|1099双向迭代加深.cpp| | + | {{折叠|1099双向迭代加深.cpp|<pre> |
#include<iostream> | #include<iostream> | ||
#include<iterator> | #include<iterator> | ||
| 第115行： | 第114行： | ||
if(f==t) | if(f==t) | ||
return 1; | return 1; | ||
| + | |||
for(int i=1;i<=n;++i) | for(int i=1;i<=n;++i) | ||
{ | { | ||
| 第155行： | 第155行： | ||
} | } | ||
return 0; | return 0; | ||
| − | } | + | }</pre>|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 展开折叠内容
|
|---|
#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;
} |
CloudLunar