CFR 386 D. Game with Points ( Dijkstra )
dp[ i ][ j ][ k ] : number of minimum moves for a state described by ( i, j, k ), i < j < k, where the three stones are located in each of them
int N; int dp[ MAXN ][ MAXN ][ MAXN ]; pii move[ MAXN ][ MAXN ][ MAXN ]; vi pre[ MAXN ][ MAXN ][ MAXN ]; string edge[ MAXN ]; typedef pair< int, vi > pivi; void solve(){ cin >> N; memset( dp, INF, sizeof( dp ) ); vi stone( 3 ); for( int i = 0; i < 3; ++i ) cin >> stone[ i ], --stone[ i ]; sort( stone.begin(), stone.end() ); dp[ stone[ 0 ] ][ stone[ 1 ] ][ stone[ 2 ] ] = 0; for( int i = 0; i < N; ++i ) cin >> edge[ i ]; vi goal = { 0, 1, 2 }; priority_queue< pivi, vector< pivi >, greater< pivi > > pq; pq.push( pivi( 0, stone ) ); while( not pq.empty() ){ int d = pq.top().first; vi t = pq.top().second; pq.pop(); if( dp[ t[ 0 ] ][ t[ 1 ] ][ t[ 2 ] ] != d ) continue; for( int i = 0; i < 3; ++i ) for( int x = 0; x < N; ++x ) if( t[ 0 ] != x and t[ 1 ] != x and t[ 2 ] != x ){ if( i == 0 ){ vi nt = { t[ 1 ], t[ 2 ], x }; sort( nt.begin(), nt.end() ); if( edge[ t[ 0 ] ][ x ] == edge[ t[ 1 ] ][ t[ 2 ] ] ) if( upmin( dp[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ], d + 1 ) ) move[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = pii( t[ i ], x ), pre[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = t, pq.push( pivi( d + 1, nt ) ); } else if( i == 1 ){ vi nt = { t[ 0 ], t[ 2 ], x }; sort( nt.begin(), nt.end() ); if( edge[ t[ 1 ] ][ x ] == edge[ t[ 0 ] ][ t[ 2 ] ] ) if( upmin( dp[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ], d + 1 ) ) move[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = pii( t[ i ], x ), pre[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = t, pq.push( pivi( d + 1, nt ) ); } else{ vi nt = { t[ 0 ], t[ 1 ], x }; sort( nt.begin(), nt.end() ); if( edge[ t[ 2 ] ][ x ] == edge[ t[ 0 ] ][ t[ 1 ] ] ) if( upmin( dp[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ], d + 1 ) ) move[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = pii( t[ i ], x ), pre[ nt[ 0 ] ][ nt[ 1 ] ][ nt[ 2 ] ] = t, pq.push( pivi( d + 1, nt ) ); } } } vp ans; for( vi u = goal; ; ){ vi pu = pre[ u[ 0 ] ][ u[ 1 ] ][ u[ 2 ] ]; if( pu.empty() ) break; ans.push_back( move[ u[ 0 ] ][ u[ 1 ] ][ u[ 2 ] ] ); u = pu; } if( dp[ goal[ 0 ] ][ goal[ 1 ] ][ goal[ 2 ] ] == INF ) cout << -1 << endl; else{ cout << ans.size() << endl; for( int i = ans.size() - 1; i >= 0; --i ) cout << ans[ i ].first + 1 << " " << ans[ i ].second + 1 << "\n"; } }