全体公開 > 合同練習会 > 20130323 > G エレベータの故障

問題の概要

壊れて, 上にはu階, 下にはd階しか下がれないエレベータがある.
下は1階から, 上はf階まであり, それらを超えた所は指定出来ない.
s階からg階まで, 最短でどれだけで着けるか.

実装の方針, 注意点

...

既に訪れた階を省いた, 幅優先探索をする.
初期化や既に訪れた階の判定のやりやすさから, d[階数]=最短ボタン押下回数+1 なる配列を用いた.

ソースコード

...

bool inRange(int a, int x, int b){
    return a <= x && x < b;
}
 
bool solve(){
    int f, s, g, up, dn;
    cin >> f >> s >> g >> up >> dn;
    if(!f) return false;
 
    int d[1000010] = {};
    d[s] = 1;
 
    queue<int> q;
    q.push(s);
 
    while(!q.empty()){
        s = q.front(); q.pop();
        if(inRange(1, s-dn, f+1) && !d[s-dn]){
            d[s-dn] = d[s] + 1;
            q.push(s-dn);
        }
        if(inRange(1, s+up, f+1) && !d[s+up]){
            d[s+up] = d[s] + 1;
            q.push(s+up);
        }
    }
    if(d[g]){
        cout << d[g]-1 << endl;
    }else{
        cout << "use the stairs" << endl;
    }
    return true;
}
 

編集

---