Cod sursa(job #2952789)

Utilizator Linca_AmaliaLinca Mihaela Amalia Linca_Amalia Data 9 decembrie 2022 22:26:59
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
queue< pair<int,int> > Q;

int di[] = {-1, -1, -1,  0, 0,  1, 1, 1};
int dj[] = { 0,  1, -1, -1, 1, -1, 0, 1};

int n, m, B[103][103][2], lRs, cRs, lJs, cJs;
char A[103][103];

bool inmat(int i, int j) {
    if (1 <= i && i <= n && 1 <= j && j <= m)
        return true;
    return false;
}

void lee( int i, int j, int k ){
    B[i][j][k] = 0;
    Q.push( make_pair(i, j) );
    while ( !Q.empty() ){
        int l = Q.front().first;
        int c = Q.front().second;
        for (int d = 0; d < 8; d++) {
            int lv = l + di[d];
            int cv = c + dj[d];
            if ( B[lv][cv][k] > B[l][c][k] + 1 && inmat(lv, cv) && A[lv][cv] != 'X'){
                B[lv][cv][k] = B[l][c][k] + 1;
                Q.push( make_pair(lv, cv) );
            }
        }
        Q.pop();
    }
}

int main(){
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; i++)
        fin.getline(A[i] + 1, 102);
    for( int i = 1; i <= n; i++ ) {
        for( int j = 1; j <= m; j++ ){
            B[i][j][0] = B[i][j][1] = n * m + 1;
            if ( A[i][j] == 'R' ){
                lRs = i;
                cRs = j;
            }
            if ( A[i][j] == 'J' ){
                lJs = i;
                cJs = j;
            }
        }
    }
    lee(lRs, cRs, 0);
    lee(lJs, cJs, 1);
    int ans = n * m + 1;
    int l = -1;
    int c = -1;
    for( int i = 1; i <= n; i++ ) {
        for( int j = 1; j <= m; j++ ){
            if (B[i][j][0] == B[i][j][1] && ans > B[i][j][0] && A[i][j] != 'X') {
                ans = B[i][j][0];
                l = i;
                c = j;
            }
        }
    }
    fout << ans + 1 << " " << l << " " << c << "\n";
    return 0;
}