|
|
| （未显示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}} | + | |
2014年12月23日 (二) 23:12的最后版本
摘要
| 题目链接 |
难度等级 |
完成状态 |
完成分数 |
最后编辑时间 |
失误原因（初次提交分数）
|
| 字符变换
|
★☆☆☆☆
|
答案正确
|
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 展开折叠内容
|
- #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