[BOJ/C+]#1697鬼ごっこ

https://www.acmicpc.net/problem/13549

問題を解く

#1697かくれんぼの問題に似ています.
しかし瞬間移動の場合は0秒後、
3種類ともキューに押し込む過程で,時間が同じものが同時にpopに入ると,時間は少ない順に現れる.
利用dequetime+1でプッシュされる一般的な移動はdeque.push_backである.
timeがそのままpushの瞬間移動はdeque.push_front、手前pushがハイライト

コード#コード#

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100000
bool visited[MAX+1];
int N,K;

int bfs(int time, int pos){

    deque<pair<int,int>> dq;
    visited[pos]=true;
    dq.push_back({time,pos});

    while(!dq.empty()){
        int curTime=dq.front().first;
        int curPos=dq.front().second;

        dq.pop_front();

        if(curPos==K) return curTime;

        //2*x
        if(2*curPos<=MAX&&!visited[2*curPos]){
            visited[2*curPos]= true;
            dq.push_front({curTime,2*curPos}); // 이동거리 (time)이 0이므로 front에 넣어줘야함@@
        }

        //x-1
        if(curPos>=1&&!visited[curPos-1]){
            visited[curPos-1]=true;
            dq.push_back({curTime+1,curPos-1});
        }

        //x+1
        if(curPos<=MAX-1&&!visited[curPos+1]){
            visited[curPos+1]= true;
            dq.push_back({curTime+1,curPos+1});
        }

    }

}

int main(){
    cin>>N>>K;
    cout<<bfs(0, N)<<"\n";
    return 0;
}

c++で初めて使うdequeはやっぱり便利~!~
注意:https://velog.io/@choiiis/C-STL-deque%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC