Cod sursa(job #2191289)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 2 aprilie 2018 13:45:23
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define MAXN 105
#define MAX 1000000000

using namespace std;

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

queue<pair<int,int> >stiva;
int romeo[MAXN][MAXN],rx,ry,julieta[MAXN][MAXN],jx,jy,n,m;
int dx[8] = {-1,-1,0,1,1,1,0,-1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};
bool v[MAXN][MAXN];

bool in_matrice(int x,int y){
    if(x >= 1 && x <= n && y >= 1 && y <= m && !v[x][y])
        return true;
    return false;
}
void lee(int x,int y,int dp[MAXN][MAXN]){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dp[i][j] = MAX;
    stiva.push({x,y});
    dp[x][y] = 1;
    int xnou,ynou;
    while(!stiva.empty()){
        int x = stiva.front().first;
        int y = stiva.front().second;
        stiva.pop();
        for(int i = 0; i < 8; i++){
            xnou = x + dx[i];
            ynou = y + dy[i];
            if(in_matrice(xnou,ynou) && dp[x][y] + 1 < dp[xnou][ynou]){
                dp[xnou][ynou] = dp[x][y] + 1;
                stiva.push({xnou,ynou});
            }
        }
    }
}
int main()
{
    in>>n>>m;
    string s;
    for(int i = 0; i <= n; i++){
        getline(in,s);
        for(int j = 0; j < s.size(); j++){
            if(s[j] == 'R')
                rx = i,ry = j+1;
            else if(s[j] == 'J')
                jx = i,jy = j+1;
            else if(s[j] == 'X')
                v[i][j+1] = true;
        }
    }

    lee(rx,ry,romeo);
    lee(jx,jy,julieta);

    int linie,coloana,dist = 2e9;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!v[i][j] && romeo[i][j] == julieta[i][j] && romeo[i][j] < dist){
                linie = i;
                coloana = j;
                dist = romeo[i][j];
            }
        }
    }
    out<<dist<<" "<<linie<<" "<<coloana;
    return 0;
}