Cod sursa(job #2824252)

Utilizator divadddDavid Curca divaddd Data 31 decembrie 2021 18:42:26
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 102
using namespace std;
int n,m,ir,jr,ij,jj,l[MAX][MAX],c[MAX][MAX];
char v[MAX][MAX];

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

/// (ir, jr) = pozitie romeo
/// (ij, jj) = pozitie julieta

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

void lee(int istart, int jstart, int istop, int jstop, int mp[MAX][MAX]){
    queue<pair<int, int>> coada;

    int dl[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
    int dc[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

    mp[istart][jstart] = 1;
    coada.push(make_pair(istart, jstart));
    while(!coada.empty()){
        int lin = coada.front().first;
        int col = coada.front().second;

        for(int k = 0; k < 8; k++){
            int linv = lin+dl[k];
            int colv = col+dc[k];

            if(inautru(linv, colv) && mp[linv][colv] == 0){
                mp[linv][colv] = mp[lin][col]+1;
                coada.push(make_pair(linv, colv));
            }
        }
        coada.pop();
    }
}

int main()
{
    fin >> n >> m;
    fin.ignore();
    for(int i = 1; i <= n; i++){
        string s;
        getline(fin, s);
        for(int j = 0; j < s.length(); j++){
            if(s[j] == 'X'){
                l[i][j+1] = -1;
            }
            if(s[j] == 'R'){
                ir = i; jr = j+1;
            }
            if(s[j] == 'J'){
                ij = i; jj = j+1;
            }
            c[i][j+1] = l[i][j+1];
        }
    }
    /// traseul lui romeo
    lee(ir, jr, ij, jj, l);
    /// traseul julietei
    lee(ij, jj, ir, jr, c);

    int tmin = 1000000007;
    int x = 0, y = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(c[i][j] == l[i][j] && l[i][j] > 0 && tmin > l[i][j]){
                x = i;
                y = j;
                tmin = l[i][j];
            }
        }
    }
    fout << tmin << " " << x << " " << y << "\n";
    return 0;
}