Cod sursa(job #2200060)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 30 aprilie 2018 10:52:25
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

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

#define DM 101

int n,m;
char mat[DM][DM];       
int distr[DM][DM],distj[DM][DM];
int di[4] = {0, 1, 0, -1};
int dj[4] = {1, 0, -1, 0};
queue < pair < int, int > > r;
queue < pair < int , int > > j;
pair < int, int > rom;
pair < int, int > jul;
pair < int, int > answer;
int atime;

bool inside(int x, int y) {
    return (x >=0 && x < n && y >= 0 && y < m);
}

int main() {
    fin >> n >> m;
    fin.get();
    for(int i = 0; i < n; i++) {
        fin.getline(mat[i], DM - 1);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mat[i][j] == 'R') {
                rom.first = i;
                rom.second = j;
            }
            if(mat[i][j] == 'J') {
                jul.first = i;
                jul.second = j;
            }
        }
    }

    r.push(make_pair(rom.first, rom.second));
    j.push(make_pair(jul.first, jul.second));

    while(!r.empty()) {
        int nodi = r.front().first;
        int nodj = r.front().second;
        r.pop();
        for(int i = 0; i < 4; i++) {
            int newi = nodi + di[i];
            int newj = nodj + dj[i];
            if(inside(newi, newj) && (mat[newi][newj] == ' ' || mat[newi][newj] == 'J') && !distr[newi][newj]) {
                r.push(make_pair(newi , newj));
                distr[newi][newj] = distr[nodi][nodj] + 1;
            }
        }
    }

    while(!j.empty()) {
        int nodi = j.front().first;
        int nodj = j.front().second;
        j.pop();
        for(int i = 0; i < 4; i++) {
            int newi = nodi + di[i];
            int newj = nodj + dj[i];
            if(inside(newi, newj) && (mat[newi][newj] == ' ' || mat[newi][newj] == 'R') && !distj[newi][newj]) {
                j.push(make_pair(newi, newj));
                distj[newi][newj] = distj[nodi][nodj] + 1;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            fout << distr[i][j] << " ";
        }
        fout << '\n';
    }
    fout << '\n';
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            fout << distj[i][j] << " ";
        }
        fout << '\n';
    }
    
    if(rom.first == jul.first && rom.second == jul.second) {
        fout << rom.first << " " << rom.second << " " << 0;
    } else {
        atime = 999999999;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(distj[i][j] == distr[i][j] && distj[i][j]) {
                    if(atime > distj[i][j]) {
                        atime = distj[i][j];
                        answer.first = i + 1;
                        answer.second = j + 1;
                    }
                }
            }
        }
    }

    fout << atime << " " << answer.first << " " << answer.second;

}