# CFR 386 D. Game with Points ( Dijkstra )

Problem - D - Codeforces

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";
}
}
```