Cod sursa(job #2181487)

Utilizator Constantin.Dragancea Constantin Constantin. Data 21 martie 2018 18:20:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>
using namespace std;

int n, m, a[110][110], b[110][110], rs=1e9, rsx, rsy, rx, ry, jx, jy;
bool M[110][110];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
string s;
queue <pair<int,int> > Q;

bool ok(int i, int j){
    if (i<1 || i>n || j<1 || j>m || M[i][j]) return 0;
    return 1;
}

void lee1(){
    while (!Q.empty()){
        int i = Q.front().first, j = Q.front().second;
        Q.pop();
        for (int dir=0; dir<8; dir++){
            int inext = i + dx[dir], jnext = j + dy[dir];
            if (ok(inext, jnext) && !a[inext][jnext]){
                a[inext][jnext] = a[i][j] + 1;
                Q.push({inext, jnext});
            }
        }
    }
}

void lee2(){
    while (!Q.empty()){
        int i = Q.front().first, j = Q.front().second;
        Q.pop();
        for (int dir=0; dir<8; dir++){
            int inext = i + dx[dir], jnext = j + dy[dir];
            if (ok(inext, jnext) && !b[inext][jnext]){
                b[inext][jnext] = b[i][j] + 1;
                Q.push({inext, jnext});
            }
        }
    }
}

int main(){
    ifstream cin ("rj.in");
    ofstream cout ("rj.out");
    cin >> n >> m;
    getline(cin, s);
    for (int i=1; i<=n; i++){
        getline(cin, s);
        for (int j=0; j<m; j++){
            if (s[j] == 'X') M[i][j+1] = 1;
            else if (s[j] == 'R') rx = i, ry = j+1;
            else if (s[j] == 'J') jx = i, jy = j+1;
        }
    }
    Q.push({rx, ry});
    a[rx][ry] = 1;
    lee1();
    Q.push({jx, jy});
    b[jx][jy] = 1;
    lee2();
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (a[i][j] && a[i][j] == b[i][j] && a[i][j] < rs){
                rs = a[i][j];
                rsx = i; rsy = j;
            }
        }
    }
    cout << rs << " " << rsx << " " << rsy;
    return 0;
}