Cod sursa(job #2297486)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 5 decembrie 2018 21:49:10
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 180;

bool bloc[MAXN][MAXN];
int drumr[MAXN][MAXN], drumj[MAXN][MAXN];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m;
queue<pair<int, int> > q;

#define x first
#define y second

bool ok(int x, int y){
    if(x > 0 && y > 0 && x <= n && y <= n){
        if(!bloc[x][y])
            return 1;
        return 0;
    }
    return 0;
}

void lee(int sx, int sy, int drum[MAXN][MAXN]){
    drum[sx][sy] = 1;
    q.push(make_pair(sx, sy));
    while(!q.empty()){
        pair<int, int> cel = q.front();
        q.pop();
        for(int d = 0; d < 8; ++d){
            int nextx = cel.x + dx[d];
            int nexty = cel.y + dy[d];
            if(ok(nextx, nexty)){
                int pas = drum[cel.x][cel.y] + 1;
                if(pas < drum[nextx][nexty]){
                    drum[nextx][nexty] = pas;
                    q.push(make_pair(nextx, nexty));
                }
            }
        }
    }
}

int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin >> n >> m;
    int rx = 0, ry = 0, jx = 0, jy = 0;
    string s;
    getline(fin, s);
    for(int i = 1; i <= n; ++i){
        getline(fin, s);
        for(int j = 0; j < m; ++j){
            if(s[j] == 'X')
                bloc[i][j + 1] = 1;
            if(s[j] == 'R'){
                rx = i;
                ry = j + 1;
            }
            if(s[j] == 'J'){
                jx = i;
                jy = j + 1;
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            drumr[i][j] = 1e9;
            drumj[i][j] = 1e9;
        }
    }
    lee(rx, ry, drumr);
    lee(jx, jy, drumj);
    int ans = 0, ansx = 0, ansy = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(drumr[i][j] < 1e9 && drumr[i][j] == drumj[i][j] && drumr[i][j] > ans){
                ans = drumr[i][j];
                ansx = i;
                ansy = j;
            }
        }
    }
    fout << ans << " " << ansx << " " << ansy;
    return 0;
}