Cod sursa(job #2249828)

Utilizator AlexHodoHodorogea Alexandru AlexHodo Data 30 septembrie 2018 11:18:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <sstream>  

using namespace std;

int N, M, ri, rj, ji, jj;
bool  harta[102][102];
int romeo[102][102], julieta[102][102];
ifstream in("rj.in");
ofstream out("rj.out");
queue < pair < int, int > > Q;
int dx[8] = {-1,-1,-1,0,0,1,1,1},
    dy[8] = {-1,0,1,-1,1,-1,0,1};

void read() {
    in>>N>>M;
    int k_line = 0;
    std::string line;
    while(std::getline(in, line)) {
        for(int j=0; j<M; j++) {
            harta[k_line][j+1] = (line[j] == ' ')? true : false;
            if(line[j] == 'R')
                ri = k_line, rj = j+1;
            else if(line[j] == 'J')
                ji = k_line, jj = j+1;
        }
        k_line += 1;
    }
    romeo[ri][rj] = 1;
    julieta[ji][jj] = 1;        
}

bool OK(int x, int y) {
    if(x<1 || x>N || y<1 || y>M)
        return false;
    if(harta[x][y] == false)
        return false;
    if((x == ri && y == rj) || (x == ji && y == jj))
        return false;
    return true;
}

void romjul() {
    // romeo
    Q.push(make_pair(ri,rj));
    while(!Q.empty()) {
        int i = Q.front().first,
            j = Q.front().second;
        Q.pop();
        for(int k=0; k<8; k++) {
            int ni = i + dx[k],
                nj = j + dy[k];
            if(OK(ni, nj)) {
                if(romeo[ni][nj] == 0) {
                    romeo[ni][nj] = romeo[i][j] + 1;
                    Q.push(make_pair(ni,nj));
                }
            }
        }
    }
    // julieta
    Q.push(make_pair(ji,jj));
    while(!Q.empty()) {
        int i = Q.front().first,
            j = Q.front().second;
        Q.pop();
        for(int k=0; k<8; k++) {
            int ni = i + dx[k],
                nj = j + dy[k];
            if(OK(ni, nj)) {
                if(julieta[ni][nj] == 0) {
                    julieta[ni][nj] = julieta[i][j] + 1;
                    Q.push(make_pair(ni,nj));
                }
            }
        }
    }
}

void find() {
    bool gasit = false;
    int x, y, val;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            if(romeo[i][j] == julieta[i][j] && romeo[i][j]>0)
                if(!gasit || romeo[i][j]<val)
                    val = romeo[i][j], gasit = true, x = i, y = j;
        }
    out<<val<<" "<<x<<" "<<y;
}

int main() {
    read();
    romjul();
    find();
}