Cod sursa(job #2672105)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 13 noiembrie 2020 06:04:24
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <cctype>
#include <string>

using namespace std;

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

int mat[105][105];
int romeo[105][105], julieta[105][105];
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int n, m;

struct Coordonate
{
    int lin, col;
};

queue <Coordonate> q;
char a[10005];

bool InBounds(Coordonate coord, int mat[105][105])
{
    return 0 < coord.lin && coord.lin <=n && 0 < coord.col && coord.col <=m;
}

bool IsFree(Coordonate coord, int mat[105][105])
{
    return mat[coord.lin][coord.col]==0;
}

void leeromeo(int x, int y)
{
    Coordonate coord;
    coord.lin=x;
    coord.col=y;
    q.push(coord);
    while (!q.empty())
    {
        Coordonate next_coord, current_coord=q.front();
        q.pop();
        for(int i=0; i<8; i++)
        {
            next_coord.lin=current_coord.lin+dir[i][0];
            next_coord.col=current_coord.col+dir[i][1];
            if(InBounds(next_coord, romeo) && IsFree(next_coord, romeo))
            {
                romeo[next_coord.lin][next_coord.col]=romeo[current_coord.lin][current_coord.col] + 1;
                q.push(next_coord);
            }
        }

    }

}
void leejulieta(int x, int y)
{
    Coordonate coord;
    coord.lin=x;
    coord.col=y;
    q.push(coord);
    while (!q.empty())
    {
        Coordonate next_coord, current_coord=q.front();
        q.pop();
        for(int i=0; i<8; i++)
        {
            next_coord.lin=current_coord.lin+dir[i][0];
            next_coord.col=current_coord.col+dir[i][1];
            if(InBounds(next_coord, julieta) && IsFree(next_coord, julieta))
            {
                julieta[next_coord.lin][next_coord.col]=julieta[current_coord.lin][current_coord.col] + 1;
                q.push(next_coord);
            }
        }

    }

}

int main()
{
    int i,j;
    int xr, yr, xj, yj;
    int valmin, imin, jmin;
    char a[105];
    fin>>n>>m>>ws;

    for(i=0; i<n; i++)
    {
        fin.getline(a, 100);
        for(j=0; j<m; j++)
        {
            if(a[j]=='R')
            {
                romeo[i+1][j+1]=1;
                xr=i+1;
                yr=j+1;
            }
            if(a[j]=='J')
            {
                julieta[i+1][j+1]=1;
                xj=i+1;
                yj=j+1;
            }
            if(a[j]=='X')
            {
                julieta[i+1][j+1]=-1;
                romeo[i+1][j+1]=-1;
            }
        }
    }
    leeromeo(xr, yr);
    leejulieta(xj, yj);


    valmin=julieta[xr][yr];
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(romeo[i][j]<1)
                continue;
            if(romeo[i][j]==julieta[i][j])
            {
                if(romeo[i][j]<valmin)
                {
                    valmin=romeo[i][j];
                    imin=i;
                    jmin=j;
                }
                if(romeo[i][j]==valmin)
                {
                    if(i<imin)
                    {
                        valmin=romeo[i][j];
                        imin=i;
                        jmin=j;
                    }
                    if(i==imin && j<jmin)
                    {
                        valmin=romeo[i][j];
                        imin=i;
                        jmin=j;
                    }

                }
            }
        }
    }
    fout<<valmin<<' '<<imin<<' '<<jmin;
}