Cod sursa(job #2438002)

Utilizator marius0072scarlat marius stefan marius0072 Data 10 iulie 2019 22:01:17
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <queue>

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

const int NMAX = 105;
int n,m,rDist[NMAX][NMAX],jDist[NMAX][NMAX];
std::pair<int,int>R,J;

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

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

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

void display(int matrix[][NMAX]){
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++)
            g << matrix[i][j] << " ";
        g << std::endl;
    }
}

int main(){
    
    f >> n >> m;
    f.get();
    
    for(int i = 0;i < n;i++){
        char line[NMAX];
        f.get(line,NMAX);
        
        for(int j = 0;j < m;j++){
            if(line[j] == ' ')
                rDist[i][j] = jDist[i][j] =  0;
            else if(line[j] == 'X')
                rDist[i][j] = jDist[i][j] = -1;
            else if(line[j] == 'R'){
                R.first = i;
                R.second = j;
            }else if(line[j] == 'J'){
                J.first = i;
                J.second = j;
            }
        }
        f.get();
    }
    
    
    Lee(rDist,R.first,R.second);
    Lee(jDist,J.first,J.second);
    
    int ans{INT_MAX};
    std::pair<int,int>sol;
    
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++){
            if(rDist[i][j] == jDist[i][j] && rDist[i][j] > 0 && rDist[i][j] < ans){
                ans = rDist[i][j];
                sol.first = i;
                sol.second = j;
            }
        }
    
    g << ans << " " << sol.first + 1 << " " << sol.second + 1;
    
    f.close();
    g.close();
    
    return 0;
}