CodeVS/1099

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
字符变换	★☆☆☆☆	答案正确	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; }