Cod sursa(job #2206008)

Utilizator TooHappyMarchitan Teodor TooHappy Data 20 mai 2018 20:34:29
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>
using namespace std;
     
ifstream in("rj.in");
ofstream out("rj.out");

bool harta[110][110], viz[110][110];
int n, m, dRomeo[110][110], dJulieta[110][110], minim = 1e9;
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

void BFSRomeo(pair< int, int > start) {
    queue< pair< int, int > > q; q.push(start);
    memset(viz, false, sizeof(viz));
    viz[start.first][start.second] = true;

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int k = 0; k < 8; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if(nx < 1 || ny < 1 || nx > n || ny > m || viz[nx][ny] || harta[nx][ny] == 0) {
                continue;
            }

            dRomeo[nx][ny] = dRomeo[x][y] + 1;
            viz[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

void BFSJulieta(pair< int, int > start) {
    queue< pair< int, int > > q; q.push(start);
    memset(viz, false, sizeof(viz));
    viz[start.first][start.second] = true;

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int k = 0; k < 8; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if(nx < 1 || ny < 1 || nx > n || ny > m || viz[nx][ny] || harta[nx][ny] == 0) {
                continue;
            }

            dJulieta[nx][ny] = dJulieta[x][y] + 1;
            viz[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    in >> n >> m; in.get();

    pair< int, int > startRomeo, startJulieta;

    for(int i = 1; i <= n; ++i) {
        char line[110]; in.getline(line, 110);

        for(int j = 0; line[j]; ++j) {
            if(line[j] == 'R') {
                harta[i][j + 1] = 0;
                startRomeo = make_pair(i, j + 1);
                continue;
            }
            if(line[j] == 'J') {
                harta[i][j + 1] = 0;
                startJulieta = make_pair(i, j  + 1);
                continue;
            }
            if(line[j] == ' ') {
                harta[i][j + 1] = 1;
            } else {
                harta[i][j + 1] = 0;
            }
        }
    }

    BFSRomeo(startRomeo);
    BFSJulieta(startJulieta);

    int x = 0, y = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(dRomeo[i][j] == dJulieta[i][j] && dRomeo[i][j] && dRomeo[i][j] < minim) {
                minim = dRomeo[i][j];
                x = i; y = j;
            }
        }
    }

    out << minim + 1 << " " << x << " " << y << "\n";

    in.close(); out.close();
     
    return 0;
}