ARC 001 B リモコン

はじめ通貨問題のように貪欲法で解いたところ撃沈。

通貨問題では、使うコインをa,b,cと昇順に並べたときbが

aの倍数、cがbの倍数であれば、貪欲法が使えるが、この問題では

プラス・マイナス両側から近づくので使えないらしい。

回答をみてBFSで実装しました。温度に対する操作回数を保存するのは嫌だったので(温度がマイナスになる可能性もあるので)、mapを使いました。初めてBFSでmapを使いましたが、相性はいいと思います。

#include <bits/stdc++.h>

using namespace std;

int main(){

    int a,b;cin>>a>>b;

    map<int,int>cnt;

    vector<int>diff={1,5,10,-1,-5,-10};

    cnt[a]=0;

    queue<int>que;

    que.push(a);

    while(!que.empty()){

        int x=que.front();que.pop();

        if(x==b)cout<<cnt[x]<<endl,exit(0);

        for(auto&& u:diff){

            int y=x+u;

            if(cnt.count(y)==0){

            cnt[y]=cnt[x]+1;

            que.push(y);

            }

        }

        }

    }