[BOJ-13549]숨바꼭질3

숨바꼭질1 에서는 2*x 이동 시 +1 시간이 더해졌는데

숨바꼭질3 에서는 2*x 이동 시 +0 시간이 지나야한다.

1. 모든 2*x 이동을 모두 한 후 Q에 모두 넣는다.

2. 나머지 이동 -1, +1 이동을 시킨다.

Q에 값을 넣으며, 값을 갱신시켜 마지막 도달지가 큐에서 뽑아지면 결과 값을 출력한다.

#include<cstdio>
#include<memory.h>
#include<queue>
using namespace std;
 
const int MAX = 100001;
int sta, fin;
int vis[MAX];
 
int main(){
    scanf("%d%d",&sta,&fin);
    memset(vis, -1, sizeof(vis));
    queue<int> q;
    q.push(sta);
    vis[sta] = 0;
    if(sta != 0){
        for(int temp = sta<<1; temp < MAX ; temp = temp << 1){
            vis[temp] = 0, q.push(temp);
        }
    }
 
    while(!q.empty()){
        int here = q.front(); q.pop();
        
        if(here == fin) break;
 
        if(here > 0){
            for(int temp = here<<1 ; temp < MAX ; temp = temp << 1){
                if(vis[temp] != -1) break;
                else if(vis[temp]==-1) vis[temp] = vis[here], q.push(temp);
            }
        }
 
        if(here-1 >= 0)
            if(vis[here-1] == -1) vis[here-1] = vis[here]+1, q.push(here-1);
        if(here+1 < MAX)
            if(vis[here+1] == -1) vis[here+1] = vis[here]+1, q.push(here+1);
 
    }
 
    printf("%d",vis[fin]);
    return 0;
}