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

著作权声明[编辑]

关于[编辑]