Cod sursa(job #1915109)

Utilizator BondyBondoc Alexandru Ionut Bondy Data 8 martie 2017 19:43:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.59 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f ( "rj.in" );
ofstream g ( "rj.out" );

int dx[8]{0,0,-1,1,-1,-1,1,1};
int dy[8]{-1,1,0,0,-1,1,-1,1};
int n, m;
int verona[ 150 ][ 150 ], drumuri = 0;
struct dr{
    int pasi, i_p, j_p;
}v[10000];
///int v_i_j[10000], v_j_j[10000], v_i_r[10000], v_j_r[10000], minim_intalnire;
pair < int, int > start_r, start_j;
queue < pair < int, int > > q;

void read(){
    f >> n >> m;
    for( int i=0 ; i<n ; i++ ){
        char linie[ 101 ];
        f.get();
        f.get( linie, 102 );
        for( int j = 0 ; j< m ; j ++ ){
            if( linie[ j ] == 'X' ){
                verona[ i ][ j ] = -1;
            }
            else if( linie[ j ] == 'R' ){
                verona[ i ][ j ] = 1;
                start_r = make_pair( i, j );
            }
            else if( linie[ j ] == 'J' ){
                verona[ i ][ j ] = 1;
                start_j = make_pair( i, j );
            }
            else{
                verona[ i ][ j ] = 0;
            }
        }
    }
}

bool aol( pair < int, int > pct ){
    if( verona[ pct.first ][ pct.second ] == -1 )
        return 0;
    if( pct.first < 0 || pct.first > n - 1 )
        return 0;
    if( pct.second < 0 || pct.second > m - 1 )
        return 0;
    return 1;
}

void lee(){
    int i, j, i_urm, j_urm;
    q.push( make_pair( start_r.first, start_r.second ) );
    q.push( make_pair( start_j.first, start_j.second ) );
    verona[ start_r.first ][ start_r.second ] = 1;
    verona[ start_j.first ][ start_j.second ] = 1;
    while( !q.empty() ){
        i= q.front().first;
        j= q.front().second;
        q.pop();
        for( int directie = 0 ; directie < 8 ; directie++ ){
            i_urm = i + dy[ directie ];
            j_urm = j + dx[ directie ];
            if( aol( make_pair( i_urm, j_urm ) ) && verona[ i_urm ][ j_urm ] == 0 ){
                verona[ i_urm ][ j_urm ] = verona[ i ][ j ] + 1;
                q.push( make_pair( i_urm, j_urm ) );
            }
        }
    }
}

void afl_cai( bool cresc, bool des_cresc, int i, int j, int pasi, int i_pasi, int j_pasi, int &drumuri ){
    if( des_cresc && verona[ i ][ j ] == 1 && i == start_j.first && j == start_j.second ){
        v[ drumuri ].pasi = pasi;
        v[ drumuri ].i_p = i_pasi;
        v[ drumuri ].j_p = j_pasi;
        drumuri ++;
    }
    else{
        for( int k = 0 ; k < 8 ; k ++ ){
            if( aol( make_pair( i + dy[ k ], j + dx[ k ] ) ) ){
                if( cresc ){
                    if( verona[ i ][ j ] < verona[ i + dy[ k ] ][ j + dx[ k ] ] ){
                        afl_cai( 1, 0, i + dy[ k ], j + dx[ k ], verona[ i + dy[ k ] ][ j + dx[ k ] ], i + dy[ k ], j + dx[ k ], drumuri );
                    }
                    else afl_cai( 0, 1, i + dy[ k ], j + dx[ k ], pasi, i_pasi, j_pasi, drumuri );
                }
                else{
                    if( verona[ i ][ j ] > verona[ i + dy[ k ] ][ j + dx[ k ] ] ){
                        afl_cai( 0, 1, i + dy[ k ], j + dx[ k ], pasi, i_pasi, j_pasi, drumuri );
                    }
                }
            }
        }
    }
}

void aleg_sol( int & drumuri ){
    int mini = v[ 0 ].pasi;
    for( int i = 1 ; i < drumuri ; i ++ ){
        if( mini > v[ i ].pasi )
            mini = v[ i ].pasi;
    }
    for( int i = 0 ; i < drumuri ; i ++ ){
        if( v[ i ].pasi > mini ){
            swap( v[ i ], v[ drumuri - 1 ] );
            drumuri --;
        }
    }
    int cop_dr = drumuri;
    if( drumuri > 1 ){
        int lmin = v[ 0 ].i_p;
        for( int i = 1 ; i < drumuri ; i ++ ){
            if( v[ i ].i_p > lmin ){
                swap( v[ i ], v[ drumuri - 1 ] );
                drumuri --;
            }
        }
        if( drumuri > 1 ){
            int cmin = v[ 0 ].j_p;
            for( int i = 1 ; i < cop_dr ; i ++ ){
                if( v[ i ].j_p > cmin ){
                    swap( v[ i ], v[ cop_dr - 1 ] );
                    cop_dr --;
                }
            }
        }
    }
}

int main()
{
    read();
    lee();
    afl_cai( 1, 0, start_r.first, start_r.second, 0, 0, 0, drumuri );
    aleg_sol( drumuri );
    g << v[ 0 ].pasi << ' ' << v[ 0 ].i_p + 1 << ' ' << v[ 0 ].j_p + 1;
    return 0;
}
    /*for( int i = 0 ; i < n ; i ++ ){
        g<< endl;
        for ( int j = 0 ; j < m ; j ++ )
            if( verona[ i ][ j ] == -1)
                g << verona[ i ][ j ] << " ";
            else if (verona[ i ][ j ] <=9)g << "  " << verona[ i ][ j ];
            else g <<  verona[ i ][ j ];
    }*/