Cod sursa(job #1686263)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 12 aprilie 2016 10:06:21
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
queue <pair<int,int> > rom;
queue <pair<int,int> > jul;
pair<int,int> aux;
int n,m,i,j,k,q,ln,col,r1,r2,j1,j2,mini=1000000;
char v[250];
int jj[101][101],r[101][101];
int dx[] = {-1,1,0,0,1,1,-1,-1};
int dy[] = {0,0,1,-1,1,-1,1,-1};
ofstream fout ("rj.out");
ifstream fin ("rj.in");
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= n ; i++)
    {
        fin.get();
        fin.get(v,250);
        for( j = 0 ; j < strlen(v) ; j++)
        {
            if( v[ j ] == 'R')
            {
                rom.push( make_pair( i , j + 1 ) );
                r1 =  i;
                r2 = j + 1;
            }
            else if( v[ j ] == 'J')
            {
                jul.push( make_pair(i , j + 1 ) );
                j1 =  i;
                j2 = j + 1;
            }
            else if( v[ j ] == 'X')
            {
                jj[ i ][ j + 1] = -1;
                r[ i ][ j + 1] = -1;
            }
        }
    }
    while(!rom.empty())
    {
        aux = rom.front();
       // fout<<"aux "<<aux.first<<" "<<aux.second<<endl;
        rom.pop();
        for(i = 0 ; i <= 7 ; i++)
        {

            ln = aux.first + dx[ i ];
            col = aux.second + dy[ i ];
            //fout<<ln<<" "<<col<<'\n';
            if(ln > 0 && col > 0 && ln <= n && col <= m)
            {
                if( r[ ln ][ col ] == 0 && (ln != r1 || col != r2 ))
                {

                    r[ ln ][ col ] = r[ aux.first ][ aux.second ] + 1;
                    rom.push(make_pair(ln,col));
                }
            }
        }
    }
    while(!jul.empty())
    {
        aux = jul.front();
        jul.pop();
        for(i = 0 ; i <= 7 ; i++)
        {
            ln = aux.first + dx[ i ];
            col = aux.second + dy[ i ];
            if(ln > 0 && col > 0 && ln <= n && col <= m)
            {
                if( jj[ ln ][ col ] == 0 && (ln != j1 || col != j2) )
                {
                    jj[ ln ][ col ] = jj[ aux.first ][ aux.second ] + 1;
                    jul.push(make_pair(ln,col));
                }
            }
        }
    }
    for( i = 1 ; i <= n ; i++)
    {
        for( j = 1 ; j <= m ; j++)
        {
            if(r[ i ][ j ] == jj[ i ][ j ] && r[ i ][ j ] > 0 )
            {
                if(r[ i ][ j ] < mini)
                {
                    mini = r[ i ][ j ];
                    ln = i;
                    col = j;
                }
            }
        }
    }
    fout<<mini + 1<<" "<<ln<<" "<<col;
}