[13913] 숨바꼭질 4

[13913] 숨바꼭질 4

#include < stdio.h >

#include < queue >

#include < stack >

#include < algorithm >

using namespace std ;

queue < pair < int , int > > q;

const int SIZE = 250001 ;

int n, k,cur,min_cnt,cnt;

bool visit[ 250003 ];

int path[ 250003 ];

int main( void ) {

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

if (n = = k) {

printf ( "0

%d" , n);

return 0 ;

}

if (n > k) {

printf ( "%d

" , n - k);

for ( int i = n; i > = k; i - - ) {

printf ( "%d " , i);

}

return 0 ;

}

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

visit[n] = true ;

while ( ! q.empty()) {

cur = q. front ().first;

cnt = q. front ().second;

q. pop ();

if (cur = = k) {

min_cnt = cnt;

break ;

}

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

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

visit[cur * 2 ] = true ;

path[cur * 2 ] = cur;

}

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

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

visit[cur + 1 ] = true ;

path[cur + 1 ] = cur;

}

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

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

visit[cur - 1 ] = true ;

path[cur - 1 ] = cur;

}

}

printf ( "%d

" , min_cnt);

stack < int > s;

int temp = k;

path[n] = n;

while (temp ! = n) {

int now = temp;

s.push(now);

temp = path[temp];

}

s.push(n);

while ( ! s.empty()) {

int now = s.top();

s. pop ();

printf ( "%d " , now);

}

return 0 ;

}

from http://dizlet.tistory.com/33 by ccl(A) rewrite - 2021-09-01 21:00:12