Cod sursa(job #2301740)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 13 decembrie 2018 15:02:03
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
int di [8] = {-1, -1, -1, 1,  1, 1,  0, 0};
int dj [8] = { 0, -1,  1, 0, -1, 1, -1, 1};
bool vizitat [102][102];
int n, m, a1, a2, b1, b2, ans = 99999999, linie, coloana;
int dist1 [103][103], dist2 [103][103];
char v [102][102];
queue <pair<int, int> > q;
pair <int, int> term;
int main (){
    fin >> n >> m; fin.get ();
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            fin.get (v [i][j]);
            if (v [i][j] == 'R')a1 = i, b1 = j;
            if (v [i][j] == 'J')a2 = i, b2 = j;
        }
        fin.get ();
    }dist1 [a1][b1] = vizitat [a1][b1] = 1;
    q.push ({a1, b1});
    while (!q.empty ()){
        term = q.front (); q.pop ();
        for (int i = 0; i < 8; i ++){
            int a = term.first + di [i];
            int b = term.second + dj [i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && !vizitat [a][b] && v [a][b] == ' '){
                vizitat [a][b] = 1;
                dist1 [a][b] = 1 + dist1 [term.first][term.second];
                q.push ({a, b});
            }
        }
    }memset (vizitat, 0, sizeof (vizitat));
    dist2 [a2][b2] = vizitat [a2][b2] = 1;
    q.push ({a2, b2});
    while (!q.empty ()){
        term = q.front (); q.pop ();
        for (int i = 0; i < 8; i ++){
            int a = term.first + di [i];
            int b = term.second + dj [i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && !vizitat [a][b] && v [a][b] == ' '){
                vizitat [a][b] = 1;
                dist2 [a][b] = 1 + dist2 [term.first][term.second];
                q.push ({a, b});
            }
        }
    }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (dist1 [i][j] == dist2 [i][j] && dist1 [i][j] > 0 && ans > dist1 [i][j])
                ans = dist1 [i][j], linie = i, coloana = j;
    fout << ans << " " << linie << " " << coloana;
    return 0;
}