比赛 20121108 评测结果 AAAAAWAAAA
题目名称 造房子的学问 最终得分 90
用户昵称 Truth.Cirno 运行时间 0.018 s
代码语言 C++ 内存使用 3.31 MiB
提交时间 2012-11-08 09:57:25
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. struct quetype
  8. {
  9. int len,tim;
  10. };
  11.  
  12. bool got[40000];
  13. queue<quetype> que;
  14.  
  15. int main(void)
  16. {
  17. freopen("wood.in","r",stdin);
  18. freopen("wood.out","w",stdout);
  19. int i,sou,tar,L[5];
  20. quetype from,to;
  21. cin>>sou>>tar;
  22. if (sou==tar)
  23. cout<<"0\n";
  24. for (i=1;i<=3;i++)
  25. cin>>L[i];
  26. cin>>L[0];
  27. to.len=sou;
  28. to.tim=0;
  29. que.push(to);
  30. got[to.len]=true;
  31. while (!que.empty())
  32. {
  33. from=que.front();
  34. to.tim=from.tim+1;
  35. /*1*/
  36. for (i=1;i<=3;i++)
  37. {
  38. to.len=from.len+L[i];
  39. if (to.len<=32767)
  40. {
  41. if (!got[to.len])
  42. {
  43. if (to.len==tar)
  44. {
  45. cout<<to.tim<<endl;
  46. return(0);
  47. }
  48. got[to.len]=true;
  49. que.push(to);
  50. }
  51. }
  52. }
  53. /*1*/
  54. /*2*/
  55. to.len=L[0];
  56. if (to.len>0&&to.len<=32767)
  57. {
  58. if (!got[to.len])
  59. {
  60. if (to.len==tar)
  61. {
  62. cout<<to.tim<<endl;
  63. return(0);
  64. }
  65. got[to.len]=true;
  66. que.push(to);
  67. }
  68. }
  69. to.len=from.len-L[0];
  70. if (to.len>0&&to.len<=32767)
  71. {
  72. if (!got[to.len])
  73. {
  74. if (to.len==tar)
  75. {
  76. cout<<to.tim<<endl;
  77. return(0);
  78. }
  79. got[to.len]=true;
  80. que.push(to);
  81. }
  82. }
  83. /*2*/
  84. /*3*/
  85. to.len=(from.len>>1);
  86. if (to.len>0)
  87. {
  88. if (!got[to.len])
  89. {
  90. if (to.len==tar)
  91. {
  92. cout<<to.tim<<endl;
  93. return(0);
  94. }
  95. got[to.len]=true;
  96. que.push(to);
  97. }
  98. }
  99. /*3*/
  100. que.pop();
  101. }
  102. cout<<"No solution.\n";
  103. return(0);
  104. }