Cod sursa(job #2437951)

Utilizator marius0072scarlat marius stefan marius0072 Data 10 iulie 2019 20:03:19
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>


std::ifstream f("rj.in");
std::ofstream g("rj.out");

const int NMAX = 105;
int n , m , matrix[NMAX][NMAX],Rdist[NMAX][NMAX],Jdist[NMAX][NMAX];

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

struct coordonates{
    int row,col;
    coordonates():row(0),col(0){}
}R,J;

bool OK(int i,int j){
    return i >= 0 && i < n && j >= 0 && j < m;
}

void Lee(int distance[][NMAX],int startx,int starty){
    distance[startx][starty] = 1;
    std::queue< std::pair<int,int> >Q;
    Q.push(std::make_pair(startx, starty));
    
    while (!Q.empty()){
        
        std::pair<int,int>coordonte = Q.front();
        Q.pop();
        
        for(int dir = 0;dir < 8;dir++){
            int new_i = coordonte.first + dx[dir];
            int new_j = coordonte.second + dy[dir];
            if(OK(new_i,new_j) && distance[new_i][new_j] == 0 && matrix[new_i][new_j] != -1){
                distance[new_i][new_j] = distance[coordonte.first][coordonte.second] + 1;
                Q.push(std::make_pair(new_i,new_j));
            }
        }
    }
}

int main(){
    
    f >> n >> m;
    f.get();
    
    for(int i = 0;i < n;i++){
        char word[NMAX];
        f.getline(word,NMAX);
        
        for (int j = 0; j < m; j++)
            if(word[j] == ' ')
                matrix[i][j] = 0;
            else if(word[j] == 'X')
                matrix[i][j] = -1;
            else if(word[j] == 'R'){
                R.row = i;
                R.col = j;
            }else if(word[j] == 'J'){
                J.row = i;
                R.col = j;
            }
        f.get();
    }
    
    Lee(Rdist,R.row,R.col);
    Lee(Jdist,J.row,J.col);
    
    coordonates sol;
    int best = (1 << 30) - 1;
    
    for (int i = 0;i < n;i++){
        for (int j = 0; j < m; j++)
            if(Rdist[i][j] == Jdist[i][j] && Rdist[i][j] < best && matrix[i][j] != -1){
                best = Rdist[i][j];
                sol.row = i;
                sol.col = j;
            }
    }
    
    g << best << " " << sol.row + 1 << " " << sol.col + 1 << '\n';
    
    
    f.close();
    g.close();
    
    return 0;
}