Cod sursa(job #2414627)

Utilizator Galatanu_BogdanGalatanu Bogdan Ioan Galatanu_Bogdan Data 24 aprilie 2019 20:27:30
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1} ;
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1} ;

bool copac[105][105];
int dist[2][105][105];

queue <pair < int , int > > q;

int n , m;

void solve (pair < int , int > sursa , int tip){
    q.push(sursa);
    dist[tip][sursa.first][sursa.second] = 0;
    
    while (!q.empty()){
        pair < int,int > now=q.front();
        q.pop();
        for (int i=0;i<8;i++){
            int x=now.first+dx[i];
            int y=now.second+dy[i];
            if (x<1 || y<1 || x>n || y>m){
                continue;
            }
            if (copac[x][y]){
                continue;
            }
            if (dist[tip][x][y]<=dist[tip][now.first][now.second]+1){
                continue;
            }
            dist[tip][x][y]=dist[tip][now.first][now.second]+1;
            q.push({x,y});
        }
    }
}

int main()
{
    fin>>n>>m;
    
    string s;
    getline(fin,s);
    
    pair < int,int > J,R;
    
    for (int i=1;i<=n;i++){
        getline(fin,s);
        for (int j=0;j<m;j++){
            if (s[j]=='R'){
                R={i,j+1};
            }
            if (s[j]=='J'){
                J={i,j+1};
            }
            if (s[j]=='X'){
                copac[i][j+1]=true;
            }
            dist[0][i][j+1]=1e9;
            dist[1][i][j+1]=1e9;
        }
    }
    
    solve(J,0);
    solve(R,1);
    
    int MIN=1e9;
    pair <int,int> part;
    
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (dist[0][i][j]==dist[1][i][j] && MIN>dist[0][i][j]){
                MIN=dist[0][i][j];
                part={i,j};
            }
        }
    }
    
    fout<<MIN+1<<" "<<part.first<<" "<<part.second;
    
    return 0;
}