Cod sursa(job #2716816)

Utilizator ElektrykT E S L A P E F E L I E Elektryk Data 5 martie 2021 18:36:41
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m;

char s[107];

int v[103][103];

int viz1[103][103];
int viz2[103][103];

int linJ, colJ, linR, colR;

queue < pair < int, int > > q;

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

int l, c;

int mn = 10137;

int main()
{
    in >> n >> m;
    in.getline ( s, 137 );
    for ( int i = 1 ; i <= n ; ++i )
    {
        in.getline ( s, 137 );
        for ( int j = 0 ; j < m ; ++j )
        {
            if ( s[j] == ' ' )
                v[i][j + 1] = 1;
            else if ( s[j] == 'X' )
                v[i][j + 1] = 0;
            else if ( s[j] == 'J' )
            {
                linJ = i;
                colJ = j + 1;
                v[i][j + 1] = 1;
            }
            else if ( s[j] == 'R' )
            {
                linR = i;
                colR = j + 1;
                v[i][j + 1] = 1;
            }
        }
    }
    /*for ( int i = 0 ; i <= n + 1 ; ++i )
        for ( int j = 0 ; j <= m + 1 ; ++j )
            v2[i][j] = v[i][j];*/
    /*for ( register int i = 0 ; i <= n + 1 ; ++i )
    {
        for ( register int j = 0 ; j <= m + 1 ; ++j )
            out << v[i][j] << " ";
        out << '\n';
    }*/
    ///romeo
    q.push ( { linR, colR } );
    viz1[linR][colR] = 1;
    while ( !q.empty () )
    {
        l = q.front ().first;
        c = q.front ().second;
        q.pop ();
        for ( int i = 1 ; i <= 8 ; ++i )
            if ( v[l + dx[i]][c + dy[i]]  &&  !viz1[l + dx[i]][c + dy[i]] )
            {
                viz1[l + dx[i]][c + dy[i]] = viz1[l][c] + 1;
                q.push ( { l + dx[i], c + dy[i] } );
            }
    }
    /*for ( register int i = 0 ; i <= n + 1 ; ++i )
    {
        for ( register int j = 0 ; j <= m + 1 ; ++j )
            out << viz1[i][j] << " ";
        out << '\n';
    }*/
    ///julieta
    q.push ( { linJ, colJ } );
    viz2[linJ][colJ] = 1;
    while ( !q.empty () )
    {
        l = q.front ().first;
        c = q.front ().second;
        q.pop ();
        for ( register int i = 1 ; i <= 8 ; ++i )
            if ( v[l + dx[i]][c + dy[i]]  &&  !viz2[l + dx[i]][c + dy[i]] )
            {
                viz2[l + dx[i]][c + dy[i]] = viz2[l][c] + 1;
                q.push ( { l + dx[i], c + dy[i] } );
            }
    }
    /*for ( register int i = 0 ; i <= n + 1 ; ++i )
    {
        for ( register int j = 0 ; j <= m + 1 ; ++j )
            out << viz2[i][j] << " ";
        out << '\n';
    }*/
    for ( register int i = 1; i <= n ; ++i )
        for ( register int j = 1 ; j <= m ; ++j )
            if ( viz1[i][j]  &&  viz1[i][j] == viz2[i][j] )
            {
                if ( mn > viz1[i][j] )
                {
                    mn = viz1[i][j];
                    l = i;
                    c = j;
                }
            }
    out << mn << " " << l << " " << c;
    return 0;
}