Cod sursa(job #2180145)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 20 martie 2018 17:41:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair< int , int > PII;

const int dirx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int diry[] = {1 ,0, -1, 0, 1, -1, 1, -1};

int n, m, DR[105][105], DJ[105][105], mn = 2e9;
char a[105][105];
bool viz[105][105];
PII R, J;

queue < PII > Q;

void Init(){
    for (int i = 1; i <= n; i++){
        viz[i][0] = viz[i][m + 1] = 1;
        for (int j = 1; j <= m; j++)
            viz[i][j] = 0, viz[0][j] = viz[n + 1][j] = 1;
    }

    while (Q.size()) Q.pop();
}

void Lee(PII dot, int d[][105]){
    Init();
    Q.push(dot);

    while (Q.size()){
        PII node = Q.front(); Q.pop();
        for (int i = 0; i < 8; i++){
            int nodex = node.x + dirx[i];
            int nodey = node.y + diry[i];
            if (viz[nodex][nodey] || a[nodex][nodey] != ' ') continue;
            viz[nodex][nodey] = 1;
            d[nodex][nodey] = d[node.x][node.y] + 1;
            Q.push({nodex, nodey});
        }
    }
}


int main(){
    ifstream cin("rj.in");
    ofstream cout("rj.out");

    cin >> n >> m;
    string s;
    getline(cin, s);

    for (int i = 1; i <= n; i++){
        getline(cin, s);
        for (int j = 1; j <= m; j++){
            a[i][j] = s[j - 1];
            if (a[i][j] == 'R') R = {i, j};
            if (a[i][j] == 'J') J = {i, j};
        }
    }
    
    Lee(R, DR);
    Lee(J, DJ);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (DR[i][j] == DJ[i][j] && DR[i][j] && mn > DR[i][j])
                mn = DR[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (DR[i][j] == DJ[i][j] && mn == DR[i][j])
                return cout << mn + 1 << " " << i << " " << j, 0;
	return 0;
}