Cod sursa(job #1349254)

Utilizator FapFapAdriana FapFap Data 20 februarie 2015 02:34:41
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 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 indX[8]= {0, -1, 0, 1, -1, -1, 1, 1}, indY[8]= {-1, 0, 1, 0, -1, 1, 1, -1};
int n, m;
bool ok;

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

void create_second_matrix(){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; 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;
}

bool in_range(int x, int y){
    if((x>=0 && x<n) && (y>=0 && y<m))  return true;
    return false;
}

void LEE(){
    q.push(make_pair(romeo.first, romeo.second));
    while(!q.empty()){
        int cur1= q.front().first;
        int cur2= q.front().second;
        q.pop();
        for(int k=0; k<8; k++){
            int i= indX[k]+ cur1;
            int j= indY[k]+ cur2;
            if(dist[0][i][j]==-1){
                q.push(make_pair(i, j));
                dist[0][i][j]= dist[0][cur1][cur2]+1;
            }
        }
    }
    q.push(make_pair(juliet.first, juliet.second));
    while(!q.empty()){
        int cur1= q.front().first;
        int cur2= q.front().second;
        q.pop();
        for(int k=0; k<8; k++){
            int i= indX[k]+ cur1;
            int j= indY[k]+ cur2;
            if(dist[1][i][j]==-1){
                q.push(make_pair(i, j));
                dist[1][i][j]= dist[1][cur1][cur2]+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();
    pair< pair<int, int>, int> finals;
    finals.second= (1<<28);
    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){
                if(dist[0][i][j] < finals.second)
                    finals.first.first= i, finals.first.second= j, finals.second= dist[0][i][j];
            }
    fout << finals.second+1 << " " << finals.first.first << " " << finals.first.second << " ";
    return 0;
}