Cod sursa(job #1692897)

Utilizator anav23Ana Vasiliu anav23 Data 21 aprilie 2016 21:57:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct punct {
    int i;
    int j;
};

int n,m,romeo[105][105],julieta[105][105];
char init[150][150];

bool isOk(punct poz) {
    return poz.i>=1&&poz.i<=n&&poz.j>=1&&poz.j<=m;
}

void lee(int harta[][105],punct start) {
    queue<punct> coada;
    punct poz,pozUrm,dir[]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
    coada.push(start);
    harta[start.i][start.j]=1;
    while(!coada.empty()) {
        poz=coada.front();
        for(int i=0;i<8;i++) {
            pozUrm={poz.i+dir[i].i,poz.j+dir[i].j};
            if(isOk(pozUrm)&&harta[pozUrm.i][pozUrm.j]==0) {
                harta[pozUrm.i][pozUrm.j]=harta[poz.i][poz.j]+1;
                coada.push(pozUrm);
            }
        }
        coada.pop();
    }
}

int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin>>n>>m;
    for(int i=0;i<=n;i++)
        fin.getline(init[i]+1,105);
    punct poz1,poz2;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
        if(init[i][j]=='X')
            romeo[i][j]=-1,julieta[i][j]=-1;
        else if(init[i][j]=='J')
            poz1={i,j};
        else if(init[i][j]=='R')
            poz2={i,j};
    }
    lee(julieta,poz1);
    lee(romeo,poz2);
    punct pozMin;
    int tMin=200;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
        int timp=max(romeo[i][j],julieta[i][j]);
        if(romeo[i][j]==julieta[i][j]&&timp<tMin&&timp>0) {
            tMin=timp;
            pozMin={i,j};
        }
    }
    fout<<tMin<<" "<<pozMin.i<<" "<<pozMin.j;
    return 0;
}