CodeVS/1099 2014年12月23日 (二) 21:47云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
字符变换	★☆☆☆☆	答案错误	80	2014/12/23 21:38:37	超时

题意

一串字符，替换成另一串字符，问最小步数（给字典）。

题解

• 迭代加深搜索（懒得写广搜，这样真的好吗……），没什么特别的
• 然后写完就发现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