Cod sursa(job #2302543)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 14 decembrie 2018 19:45:50
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 105;

int ma[NMAX][NMAX];
int romeo[NMAX][NMAX];
int julieta[NMAX][NMAX];

queue < pair<int,int> > q;
int dx[9] = {0,-1,-1,0,1,1,1,0,-1};
int dy[9] = {0,0,1,1,1,0,-1,-1,-1};

int n,m;

bool interior(int x,int y)
{
    if(x<=n and x>=1 and y<=m and y>=1) return 1;
    return 0;
}

void leeromeo(int x,int y)
{
    q.push(make_pair(x,y));
    int coordx,coordy;
    while(!q.empty())
    {
        pair<int,int> aux = q.front();
        q.pop();
        for(int i=1;i<=8;i++)
        {
            coordx=aux.first+dx[i];
            coordy=aux.second+dy[i];
            if(interior(coordx,coordy)==1 and romeo[coordx][coordy]==0 and ma[coordx][coordy]==0)
            {
                romeo[coordx][coordy]=romeo[aux.first][aux.second]+1;
                q.push(make_pair(coordx,coordy));
            }
        }
    }
}
void leejulieta(int x,int y)
{
    q.push(make_pair(x,y));
    int coordx,coordy;
    while(!q.empty())
    {
        pair<int,int> aux = q.front();
        q.pop();
        for(int i=1;i<=8;i++)
        {
            coordx=aux.first+dx[i];
            coordy=aux.second+dy[i];
            if(interior(coordx,coordy)==1 and julieta[coordx][coordy]==0 and ma[coordx][coordy]==0)
            {
                julieta[coordx][coordy]=julieta[aux.first][aux.second]+1;
                q.push(make_pair(coordx,coordy));
            }
        }
    }
}

char c[NMAX];

int main()
{
    int xr,yr,xj,yj;
    fin >> n >> m;
    fin.get();
    for(int i=1;i<=n;i++)
    {
       fin.getline(c,NMAX-4);
       /// fout << c[0] << ' ' << c[1] << ' ' << c[2] << '\n';
       for(int j=0;c[j]!='\n';j++)
       {
            if(c[j]=='X') ma[i][j+1]=1;
            if(c[j]=='R')
            {
                xr=i;
                yr=j+1;
            }
            if(c[j]=='J')
            {
                xj=i;
                yj=j+1;
            }
       }
    }
    leeromeo(xr,yr);
    leejulieta(xj,yj);
    int minim=NMAX*NMAX;
    int xrasp,yrasp;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(romeo[i][j]!=0 and romeo[i][j]==julieta[i][j] and romeo[i][j]<minim)
            {
                minim=romeo[i][j];
                xrasp=i;
                yrasp=j;
            }
        }
    }
    fout << minim+1 << ' ' << xrasp << ' ' << yrasp;
    return 0;
}