Cod sursa(job #2496061)

Utilizator matei8787Matei Dobrea matei8787 Data 20 noiembrie 2019 10:20:27
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
struct ura{
    int x,y;
};
ura q[105*105*4],romeo,julieta,ans;
int leer[105][105],leej[105][105],n,m;
int dx[] = { -1 , -1 , 0 , 1 , 1 , 1 , 0 , -1 };
int dy[] = { 0 , 1 , 1 , 1 , 0 , -1 , -1 , -1 };
int minim=2000000000;
void Leer()
{
    int inc,sf;
    inc = sf = 1;
    q[sf] = romeo;
    leer[romeo.x][romeo.y] = inc;
    while ( inc <= sf ){
        for ( int i = 0 ; i <= 7 ; i++ ){
            ura vecin;
            vecin.x = q[inc].x + dx[i];
            vecin.y = q[inc].y + dy[i];
            if ( leer[vecin.x][vecin.y] == 0 ){
                leer[vecin.x][vecin.y] = leer[q[inc].x][q[inc].y] + 1;
                q[++sf] = vecin;
            }
        }
        inc++;
    }
}
void Leej()
{
    int inc,sf;
    inc = sf = 1;
    q[sf] = julieta;
    leej[julieta.x][julieta.y] = inc;
    while ( inc <= sf ){
        for ( int i = 0 ; i <= 7 ; i++ ){
            ura vecin;
            vecin.x = q[inc].x + dx[i];
            vecin.y = q[inc].y + dy[i];
            if ( leej[vecin.x][vecin.y] == 0 ){
                leej[vecin.x][vecin.y] = leej[q[inc].x][q[inc].y] + 1;
                q[++sf] = vecin;
            }
        }
        inc++;
    }
}
void bordarer()
{
    for ( int i = 0 ; i <= n + 1 ; i++ ){
        leer[i][0] = -1;
        leer[i][m+1] = -1;
    }
    for ( int i = 0 ; i <= n + 1 ; i++ ){
        leer[0][i] = -1;
        leer[n+1][i] = -1;
    }
}
void bordarej()
{
    for ( int i = 0 ; i <= n + 1 ; i++ ){
        leej[i][0] = -1;
        leej[i][m+1] = -1;
    }
    for ( int i = 0 ; i <= n + 1 ; i++ ){
        leej[0][i] = -1;
        leej[n+1][i] = -1;
    }
}
void citire()
{
    in>>n>>m;
    char c;
    for ( int i = 1 ; i <= n ; i++ ){
        in.get(c);
        for ( int j = 1 ; j <= m ; j++ ){
            in.get(c);
            if ( c == 'R' ){
                romeo.x = i;
                romeo.y = j;
                leer[i][j] = leej[i][j] = 0;
            }
            if ( c == 'J' ){
                julieta.x = i;
                julieta.y = j;
                leer[i][j] = leej[i][j] = 0;
            }
            if ( c == ' ' ){
                leej[i][j] = leer[i][j] = 0;
            }
            if ( c == 'X' )
                leej[i][j] = leer[i][j] = -1;
        }
    }
    bordarej();
    bordarer();
}
void rezolvare()
{
    Leej();
    Leer();
    for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ){
            if ( leej[i][j] == leer[i][j] && minim > leej[i][j] && leer[i][j] != -1 ){
                minim = leej[i][j];
                ans.x = i;
                ans.y = j;
            }
        }
    }
}
int main()
{
    citire();
    rezolvare();
    out<<minim<<" "<<ans.x<<" "<<ans.y;
}