Cod sursa(job #2049805)

Utilizator denniscrevusDennis Curti denniscrevus Data 27 octombrie 2017 17:40:17
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#define NMAX 102

using namespace std;

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

struct elem
{
    int x;
    int y;
    int pasi;
}qu[ NMAX * NMAX ], unu, doi;

int n, i, m, check, j, x1, y1, x2, y2, bJ[ NMAX ][ NMAX ], bR[ NMAX ][ NMAX ];
char x;

int dx[] = { 0, 0, 1, -1, -1, 1, 1, -1};
int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1};

void borduri()
{
    for ( i = 0; i <= n + 1; i ++ )
        bR[ i ][ 0 ] = bR[ i ][ m + 1 ] = bJ[ i ][ 0 ] = bJ[ i ][ m + 1 ] = -1;

    for ( i = 0; i <= m + 1; i ++ )
        bR[ 0 ][ i ] = bR[ n + 1 ][ i ] = bJ[ 0 ][ i ] = bJ[ n + 1 ][ i ] = -1;
}

void bfs( int x, int y, bool z )
{
    int inc = 1, sf = 1;

    qu[ inc ] . x = x;
    qu[ inc ] . y = y;
    qu[ inc ] . pasi = 1;

    while ( sf >= inc )
    {
        unu = qu[ inc ++ ];

        for (int k = 0; k <= 7; k ++ )
        {
            doi . x = unu . x + dx[ k ];
            doi . y = unu . y + dy[ k ];
            doi . pasi = unu . pasi + 1;

            if ( !z && !bR[ doi . x ][ doi . y ] )
            {
                qu[ ++ sf ] = doi;
                bR[ doi . x ][ doi . y ] = doi . pasi;
            }
            else if ( z && !bJ[ doi . x ][ doi . y ] )
            {
                qu[ ++ sf ] = doi;
                bJ[ doi . x ][ doi . y ] = doi . pasi;
            }
        }
    }
}

void citire()
{
    f >> n >> m;
    f . get ( x );

    for ( i = 1; i <= n; i ++ )
    {
        check = 0;

        for ( j = 1; j <= m; j ++ )
        {
            f . get ( x );

            if ( x == 'R' )
            {
                x1 = i;
                y1 = j;
                bR[ i ][ j ] = 1;
            }
            if ( x == 'J' )
            {
                x2 = i;
                y2 = j;
                bJ[ i ][ j ] = 1;
            }
            if ( x == 'X' )
                bR[ i ][ j ] = bJ[ i ][ j ] = -1;

            if ( x == '\n')
                check = 1;
        }

        if ( !check )
            f . get ( x );
    }
}

void rezolvare()
{
    for ( i = 1; i <= n; i ++ )
        for ( j = 1; j <= m; j ++ )
        {
            if ( bR[ i ][ j ] == bJ[ i ][ j ] && bR[ i ][ j ] > 0 )
            {
                g << bR[ i ][ j ] << " " << i << " " << j << "\n";
                return;
            }

        }
}

int main()
{
    citire();
    borduri();

    bfs( x1, y1, 0 );
    bfs( x2, y2, 1 );

    rezolvare();
}