[12851] 숨바꼭질 2

[12851] 숨바꼭질 2

#include < limits.h >

#include < stdio.h >

#include < algorithm >

#include < queue >

using namespace std ;

queue < pair < int , int > > q;

const int INF = INT_MAX;

const int SIZE = 100001 ;

int n, k;

bool visit[ 100001 ];

int main( void ) {

int cur = 0 , min_cnt = 0 , i, cnt = 0 , ans = 1 ;

bool find = false ;

scanf ( "%d %d" , & n, & k);

if (n = = k) {

printf ( "0

1" );

return 0 ;

}

q.push( make_pair (n, 0 ));

visit[n] = true ;

while ( ! q.empty()) {

cur = q. front ().first;

cnt = q. front ().second;

q. pop ();

visit[cur] = true ;

if (find = = true & & cnt = = min_cnt & & cur = = k) {

ans + + ;

}

if (cur = = k & & find = = false ) {

find = true ;

min_cnt = cnt;

}

if (cur * 2 < = SIZE & & ! visit[cur * 2 ]) {

q.push( make_pair (cur * 2 , cnt + 1 ));

}

if (cur + 1 < = SIZE & & ! visit[cur + 1 ]) {

q.push( make_pair (cur + 1 , cnt + 1 ));

}

if (cur - 1 > = 0 & & ! visit[cur - 1 ]) {

q.push( make_pair (cur - 1 , cnt + 1 ));

}

}

printf ( "%d

%d" , min_cnt, ans);

return 0 ;

}

from http://dizlet.tistory.com/121 by ccl(A) rewrite - 2021-10-08 01:00:21