Cod sursa(job #2408483)

Utilizator KRAKEN01Sergiu Adrian KRAKEN01 Data 17 aprilie 2019 23:55:29
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <queue>
//#include <iostream>
using namespace std;

ifstream finn ("rj.in");
ofstream foutt ("rj.out");
bool copac[105][105];
int dist[2][105][105]; //tip , i , j

queue <pair < int , int > > q;

int n , m;
int dx[]={-1, -1, -1, 0, 0, 1, 1, 1};
int dy[]={-1, 0, 1, -1, 1, -1, 0, 1};
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});
        }
    }
}
finn>>n>>m;
 string s;
    getline(finn,s);

    pair < int , int > J , R;

    for (int i=1; i<=n; i++){
        getline(finn , 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};
            }
        }
    }

    foutt<<MIN+1<<" "<<part.first<<" "<<part.second<<'\n';

    return 0;
}