Cod sursa(job #1932676)

Utilizator Alex18maiAlex Enache Alex18mai Data 19 martie 2017 23:22:41
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <queue>

using namespace std ;

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

const int MAX = 179 ;

queue < pair<int, int> > Q;
char sir[MAX];
bool cant [MAX][MAX] ;
int distr [MAX][MAX] ;
int distj [MAX] [MAX];

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

bool inside (int i, int j, int n, int m)
{
    return i >= 1 and j >= 1 and i <= n and j <= m ;
}

int main ()
{
    int n, m ;
    cin >> n >> m ;
    cin.get();
    int xr, yr, xj, yj;
    for (int i=1; i<=n; i++){
        cin.getline(sir+1, MAX);
        for (int j=1; j<=m; j++){
            if (sir[j]=='R'){
                xr=i;
                yr=j;
            }
            if (sir[j]=='J'){
                xj=i;
                yj=j;
            }
            if (sir[j]=='X'){
                cant [i][j] = true;
            }
            distr [i][j] = 1e9 ;
            distj [i][j] = 1e9 ;
        }
    }
    //cout<<xr<<" "<<yr<<" "<<xj<<" "<<yj;
    distr [xr][yr] = 1 ;
    int xr_neigh;
    int yr_neigh;
    Q.push (make_pair(xr,yr)) ;
    while (!Q.empty()) {
        pair <int, int> curr = Q.front() ;
        Q.pop() ;
        for (int k = 0; k <= 7; ++ k) {
            xr_neigh = curr.first + dx [k] ;
            yr_neigh = curr.second + dy [k] ;
            if (inside (xr_neigh, yr_neigh, n, m) == false) {
                continue ;
            }
            if (cant [xr_neigh][yr_neigh] == true) {
                continue ;
            }
            if (distr [xr_neigh][yr_neigh] > distr [curr.first][curr.second] + 1) {
                distr [xr_neigh][yr_neigh] = distr [curr.first][curr.second] + 1 ;
                Q.push (make_pair (xr_neigh, yr_neigh)) ;
            }
        }
    }
    int xj_neigh;
    int yj_neigh;
    distj [xj][yj] = 1 ;
    Q.push (make_pair(xj,yj)) ;
    while (!Q.empty()) {
        pair <int, int> curj = Q.front() ;
        Q.pop() ;
        for (int k = 0; k <= 7; ++ k) {
            xj_neigh = curj.first + dx [k] ;
            yj_neigh = curj.second + dy [k] ;
            if (inside (xj_neigh, yj_neigh, n, m) == false) {
                continue ;
            }
            if (cant [xj_neigh][yj_neigh] == true) {
                continue ;
            }
            if (distj [xj_neigh][yj_neigh] > distj [curj.first][curj.second] + 1) {
                distj [xj_neigh][yj_neigh] = distj [curj.first][curj.second] + 1 ;
                Q.push (make_pair (xj_neigh, yj_neigh)) ;
            }
            if (distr [xj_neigh][yj_neigh]==distj [xj_neigh][yj_neigh]){
                cout<<distj [xj_neigh][yj_neigh]<<" "<<xj_neigh<<" "<<yj_neigh;
                return 0;
            }
        }
    }
    return 0 ;
}