Cod sursa(job #1773966)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 8 octombrie 2016 13:39:51
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
#define llu long long unsigned

char h[105][105];
int dpR[105][105], dpJ[105][105];
queue <pair <int, int>> q;
int d[4][2] = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};

void romeoLee(int sx, int sy){
    dpR[sx][sy] = 1;
    q.push({sx, sy});
    int x,y,nx,ny,k;
    while(q.empty() == false){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(k = 0;k < 4;k++){
            nx = x + d[k][0];
            ny = y + d[k][1];
            if(h[nx][ny] != 'X' && dpR[nx][ny] == 0){
                dpR[nx][ny] = dpR[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

void julietLee(int sx, int sy){
    dpJ[sx][sy] = 1;
    q.push({sx, sy});
    int x,y,nx,ny,k;
    while(q.empty() == false){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(k = 0;k < 4;k++){
            nx = x + d[k][0];
            ny = y + d[k][1];
            if(h[nx][ny] != 'X' && dpJ[nx][ny] == 0){
                dpJ[nx][ny] = dpJ[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main(){
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    int n,m,i,j,mn;
    char ch;
    fin>>n>>m;
    noskipws(fin);
    fin>>ch;
    for(i = 1;i <= n;i++){
        bool ok = true;
        for(j = 1;j <= m;j++){
            fin>>h[i][j];
            if(h[i][j] == '\n'){
                ok = false;
                break;
            }
        }
        for(;j <= m;j++){
            h[i][j] = (char)32;
        }
        if(ok == true){
            fin>>ch;
        }
    }
    for(i = 0;i <= n+1;i++){
        h[i][0] = h[i][m+1] = 'X';
    }
    for(i = 0;i <= m+1;i++){
        h[0][i] = h[n+1][i] = 'X';
    }
    int x,y;
    x = 0;
    for(i = 1;i <= n && x == 0;i++){
        for(j = 1;j <= m && x == 0;j++){
            if(h[i][j] == 'R'){
                x = i;
                y = j;
            }
        }
    }
    romeoLee(x, y);
    x = 0;
    for(i = 1;i <= n && x == 0;i++){
        for(j = 1;j <= m && x == 0;j++){
            if(h[i][j] == 'J'){
                x = i;
                y = j;
            }
        }
    }
    julietLee(x, y);
    x = 0;
    y = 0;
    mn = 1e9;
    for(i = 1;i <= n;i++){
        for(j = 1;j <= m;j++){
            if(h[i][j] != 'X'){
                if(dpR[i][j] && dpR[i][j] == dpJ[i][j] && dpR[i][j] < mn){
                    mn = dpR[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }
    fout<<mn-1<<' '<<x<<' '<<y;
    return 0;
}