캣치미이프유캔

AOJ 캣치미이프유캔 1697

SOL)

BFS 문제

갈 수 있는 범위 체크 해주고 방문했던 좌표 체크
X-1, X+1, 2*X인 지점을 큐에 넣고 탐색

[-] Collapse

#include<cstdio>
#include<queue>
bool visit[100001];
int X, END;
bool canPush(int val){
    if (val < 0 || val > 100000 || visit[val]) return false;
    else{ visit[val] = true; return true; }
}
int BFS(){
    int cost = 0;
    std::queue<int> q;
    q.push(X);
    visit[X] = true;
    while (!q.empty()){
        int size = q.size();
        for (int l = 0; l < size; l++){
            int here = q.front();
            q.pop();
            if (here == END) return cost;
            if (canPush(here - 1)) q.push(here - 1);
            if (canPush(here + 1)) q.push(here + 1);
            if (canPush(here * 2)) q.push(here * 2);
        }
        cost++;
    }
    return -1;
}

int main(){
    scanf("%d%d", &X, &END);
    printf("%d", BFS());
}