Logo CloudLunar

“CodeVS/1099”的版本间的差异

（以“ 分类:深度优先搜索分类:广度优先搜索 ==摘要== {{信息题|字符变换|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}}

2014年12月23日 (二) 21:48的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
字符变换 ★☆☆☆☆ 答案正确 100 2014/12/23 21:38:37 80（超时）

题意

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

题解

  • 迭代加深搜索（懒得写广搜，这样真的好吗……），没什么特别的
  • 然后写完就发现T了
  • 优化就是改成双向搜索，由于是指数型增长，这样可以提升效率非常多。

代码

1099朴素迭代加深(80分).cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. string f,t,df[10],dt[10];
  5. int n,depth;
  6. void init();
  7. const bool work (const int&);
  8. const bool dfs(const string & f,const int &depth);
  9. int main()
  10. {
  11.     init();
  12.     for(int i=1;i<=10;++i)//deeper the depth step by step
  13.     {
  14.         if(work(i))
  15.         {
  16.             cout<<i<<endl;
  17.             return 0;
  18.         }
  19.     }
  20.     cout<<"NO ANSWER!"<<endl;
  21.     return 0;
  22. }
  23. void init()
  24. {
  25.     cin>>f>>t;
  26.     for(n=1;cin>>df[n]>>dt[n];++n);
  27.     --n;
  28. }
  29. const bool work(const int &depth)
  30. {
  31.     ::depth=depth;
  32.     return dfs(f,0);
  33. }
  34. const bool dfs(const string & f,const int &depth)
  35. {
  36.     if(depth>::depth)
  37.         return 0;
  38.     if(f==t)
  39.         return 1;
  40.     for(int i=1;i<=n;++i)
  41.     {
  42.         int pos=f.find(df[i]);
  43.         if(pos==string::npos)
  44.             continue;
  45.         string nt=f;
  46.         nt.replace(pos,df[i].size(),dt[i]);
  47.         if(dfs(nt,depth+1))
  48.             return 1;
  49.     }
  50.     return 0;
  51. }
  52.  
1099双向迭代加深.cpp
展开折叠内容
code1099s
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/1099&oldid=851”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]