Cod sursa(job #1343878)

Utilizator FapFapAdriana FapFap Data 16 februarie 2015 00:10:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.86 kb
#include <iostream>
#include <fstream>
#include <queue>
#define nmax 105
#define inf -100000
using namespace std;

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

char a[nmax][nmax];
int dist[2][nmax][nmax];
int n, m;
bool ok;

queue< pair<int, int> > q;
pair<int, int> romeo, juliet;

void create_second_matrix(){
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=m+1; j++)
            if(a[i][j]== ' ' && i>0 && j>0 && i<n+1 && j<m+1)   dist[0][i][j]= -1, dist[1][i][j]= -1;
    else    dist[0][i][j]= inf, dist[1][i][j]= inf;
    dist[0][romeo.first][romeo.second]= 0;
    dist[1][juliet.first][juliet.second]= 0;
    dist[0][juliet.first][juliet.second]= -1;
    dist[1][romeo.first][romeo.second]= -1;
}

void LEE(){
    q.push(make_pair(romeo.first, romeo.second));
    while(!q.empty()){
        int i= q.front().first;
        int j= q.front().second;
        q.pop();
        if(dist[0][i-1][j]==-1){
            q.push(make_pair(i-1, j));
            dist[0][i-1][j]= dist[0][i][j]+1;
        }
        if(dist[0][i][j+1]==-1){
            q.push(make_pair(i, j+1));
            dist[0][i][j+1]= dist[0][i][j]+1;
        }
        if(dist[0][i+1][j]==-1){
            q.push(make_pair(i+1, j));
            dist[0][i+1][j]= dist[0][i][j]+1;
        }
        if(dist[0][i][j-1]==-1){
            q.push(make_pair(i, j-1));
            dist[0][i][j-1]= dist[0][i][j]+1;
        }
        if(dist[0][i+1][j+1]==-1){
            q.push(make_pair(i+1, j+1));
            dist[0][i+1][j+1]= dist[0][i][j]+1;
        }
        if(dist[0][i-1][j-1]==-1){
            q.push(make_pair(i-1, j-1));
            dist[0][i-1][j-1]= dist[0][i][j]+1;
        }
        if(dist[0][i+1][j-1]==-1){
            q.push(make_pair(i+1, j-1));
            dist[0][i+1][j-1]= dist[0][i][j]+1;
        }
        if(dist[0][i-1][j+1]==-1){
            q.push(make_pair(i-1, j+1));
            dist[0][i-1][j+1]= dist[0][i][j]+1;
        }
    }
    q.push(make_pair(juliet.first, juliet.second));
    while(!q.empty()){
        int i= q.front().first;
        int j= q.front().second;
        q.pop();
        if(dist[1][i-1][j]==-1){
            q.push(make_pair(i-1, j));
            dist[1][i-1][j]= dist[1][i][j]+1;
        }
        if(dist[1][i][j+1]==-1){
            q.push(make_pair(i, j+1));
            dist[1][i][j+1]= dist[1][i][j]+1;
        }
        if(dist[1][i+1][j]==-1){
            q.push(make_pair(i+1, j));
            dist[1][i+1][j]= dist[1][i][j]+1;
        }
        if(dist[1][i][j-1]==-1){
            q.push(make_pair(i, j-1));
            dist[1][i][j-1]= dist[1][i][j]+1;
        }
        if(dist[1][i+1][j+1]==-1){
            q.push(make_pair(i+1, j+1));
            dist[1][i+1][j+1]= dist[1][i][j]+1;
        }
        if(dist[1][i-1][j-1]==-1){
            q.push(make_pair(i-1, j-1));
            dist[1][i-1][j-1]= dist[1][i][j]+1;
        }
        if(dist[1][i+1][j-1]==-1){
            q.push(make_pair(i+1, j-1));
            dist[1][i+1][j-1]= dist[1][i][j]+1;
        }
        if(dist[1][i-1][j+1]==-1){
            q.push(make_pair(i-1, j+1));
            dist[1][i-1][j+1]= dist[1][i][j]+1;
        }
    }
}

int main(){
    string s;
    fin.sync_with_stdio(false);
    fin >> n >> m;
    fin.get();
    for(int i=1; i<=n; i++){
        getline(fin, s);
        for(int j=0; j<m; j++){
            a[i][j+1]= s[j];
            if(s[j]=='R')   romeo.first= i, romeo.second= j+1;
            if(s[j]=='J')   juliet.first= i, juliet.second= j+1;
        }
    }
    create_second_matrix();
    LEE();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(dist[0][i][j]==dist[1][i][j] && dist[0][i][j]!= inf && dist[0][i][j]!= -1){
                fout << dist[0][i][j]+1 << " " << i << " " << j << " ";
                return 0;
            }
    return 0;
}