Cod sursa(job #2186409)

Utilizator TooHappyMarchitan Teodor TooHappy Data 25 martie 2018 16:29:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <bits/stdc++.h>
using namespace std;
     
ifstream in("rj.in");
ofstream out("rj.out");

int n, m, distRomeo[110][110], distJulieta[110][110];
bool a[110][110], viz[110][110];
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 > startNode) {
    queue< pair< int, int > > q; q.push(startNode);
    memset(viz, 0, sizeof(viz));

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

        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] == 1 || a[nx][ny] == 0) {
                continue;
            }

            distRomeo[nx][ny] = distRomeo[x][y] + 1;
            q.push(make_pair(nx, ny));
            viz[nx][ny] = 1;
        }
    }
}

void BFSJulieta(pair< int, int > startNode) {
    queue< pair< int, int > > q; q.push(startNode);
    memset(viz, 0, sizeof(viz));

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

        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] == 1 || a[nx][ny] == 0) {
                continue;
            }

            distJulieta[nx][ny] = distJulieta[x][y] + 1;
            q.push(make_pair(nx, ny));
            viz[nx][ny] = 1;
        }
    }
}

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') {
                a[i][j + 1] = 0;
                startRomeo = make_pair(i, j + 1);
                continue;
            }
            if(line[j] == 'J') {
                a[i][j + 1] = 0;
                startJulieta = make_pair(i, j + 1);
                continue;
            }
            if(line[j] == ' ') {
                a[i][j + 1] = 1;
            } else {
                a[i][j + 1] = 0;
            }
        }
    }

    BFSRomeo(startRomeo);
    BFSJulieta(startJulieta);

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(distRomeo[i][j] == distJulieta[i][j] && distRomeo[i][j] != 0) {
                out << distRomeo[i][j] + 1 << " " << i << " " << j << '\n';
                break;
            }
        }
    }

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