| 比赛 | 
    20121108 | 
    评测结果 | 
    AWAAAWAAWA | 
    | 题目名称 | 
    造房子的学问 | 
    最终得分 | 
    70 | 
    | 用户昵称 | 
    王者自由 | 
    运行时间 | 
    0.311 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    3.15 MiB  | 
    | 提交时间 | 
    2012-11-08 10:52:47 | 
显示代码纯文本
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 32767 + 10;
int n, m, r, l[3], s;
int BFS() {
    queue<pair<int, int> > q;
    bool v[N] = {0};
    q.push(make_pair(n, 0));
    while(!q.empty()) {
        vector<int> o;
        int u = q.front().first, d = q.front().second; q.pop();
        if(v[u]) continue;
        v[u] = 1;
        if(u == m) return d;
        if(u > r)
            o.push_back(r), o.push_back(u - r);
        if(u > 1)
            o.push_back(u / 2);
        for(int i=0; i<3; i++) if(u + l[i] <= m)
            o.push_back(u + l[i]);
        for(int i=0; i<o.size(); i++)
            q.push(make_pair(o[i], d + 1));
    } return false;
}
int main() {
    freopen("wood.in", "r", stdin);
    freopen("wood.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=0; i<3; i++)
        scanf("%d", l+i);
    scanf("%d", &r);
    if(s = BFS())
        printf("%d\n", s);
    else printf("No solution.\n");
    return 0;
}