比赛 | 20121108 | 评测结果 | AAAAAWAAAA |
---|---|---|---|
题目名称 | 造房子的学问 | 最终得分 | 90 |
用户昵称 | Truth.Cirno | 运行时间 | 0.018 s |
代码语言 | C++ | 内存使用 | 3.31 MiB |
提交时间 | 2012-11-08 09:57:25 | ||
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <queue>
- using namespace std;
- struct quetype
- {
- int len,tim;
- };
- bool got[40000];
- queue<quetype> que;
- int main(void)
- {
- freopen("wood.in","r",stdin);
- freopen("wood.out","w",stdout);
- int i,sou,tar,L[5];
- quetype from,to;
- cin>>sou>>tar;
- if (sou==tar)
- cout<<"0\n";
- for (i=1;i<=3;i++)
- cin>>L[i];
- cin>>L[0];
- to.len=sou;
- to.tim=0;
- que.push(to);
- got[to.len]=true;
- while (!que.empty())
- {
- from=que.front();
- to.tim=from.tim+1;
- /*1*/
- for (i=1;i<=3;i++)
- {
- to.len=from.len+L[i];
- if (to.len<=32767)
- {
- if (!got[to.len])
- {
- if (to.len==tar)
- {
- cout<<to.tim<<endl;
- return(0);
- }
- got[to.len]=true;
- que.push(to);
- }
- }
- }
- /*1*/
- /*2*/
- to.len=L[0];
- if (to.len>0&&to.len<=32767)
- {
- if (!got[to.len])
- {
- if (to.len==tar)
- {
- cout<<to.tim<<endl;
- return(0);
- }
- got[to.len]=true;
- que.push(to);
- }
- }
- to.len=from.len-L[0];
- if (to.len>0&&to.len<=32767)
- {
- if (!got[to.len])
- {
- if (to.len==tar)
- {
- cout<<to.tim<<endl;
- return(0);
- }
- got[to.len]=true;
- que.push(to);
- }
- }
- /*2*/
- /*3*/
- to.len=(from.len>>1);
- if (to.len>0)
- {
- if (!got[to.len])
- {
- if (to.len==tar)
- {
- cout<<to.tim<<endl;
- return(0);
- }
- got[to.len]=true;
- que.push(to);
- }
- }
- /*3*/
- que.pop();
- }
- cout<<"No solution.\n";
- return(0);
- }