[1525] 퍼즐

[1525] 퍼즐

#include < bits / stdc + + .h >

using namespace std ;

typedef struct {

string s;

int turn;

} state;

queue < state > q;

set < string > st;

string cmp = "123456780" ;

int dy[ 4 ] = { 3 , - 3 , 1 , - 1 };

int main( void ) {

string in = "" ;

in.resize( 9 );

for ( int i = 0 ; i < 9 ; i + + ) cin > > in[i];

q.push({in, 0 });

st.insert(in);

while ( ! q.empty()) {

auto cur = q. front ();

q. pop ();

int idx = cur.s.find( '0' );

if (cur.s = = cmp) {

cout < < cur.turn;

return 0 ;

}

for ( int i = 0 ; i < 4 ; i + + ) {

int nxt = idx + dy[i];

if (nxt < 0 | | nxt > = 9 ) continue ;

if (idx = = 2 & & nxt = = 3 ) continue ;

if (idx = = 5 & & nxt = = 6 ) continue ;

if (idx = = 3 & & nxt = = 2 ) continue ;

if (idx = = 6 & & nxt = = 5 ) continue ;

string temp = cur.s;

swap(temp[idx], temp[nxt]);

if (st.find(temp) = = st. end ()) {

st.insert(temp);

q.push({temp, cur.turn + 1 });

}

}

}

cout < < - 1 ;

return 0 ;

}

from http://dizlet.tistory.com/265 by ccl(A) rewrite - 2021-12-22 12:26:35