Cod sursa(job #2911827)

Utilizator andreibrosPeta Andrei Mathias andreibros Data 2 iulie 2022 15:29:35
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n,m;
struct celula
{
    int lin;
    int col;
    celula()
    {
    }
    celula(int l, int c)
    {
        lin=l;
        col=c;
    }
};
queue <struct celula> coada;
int di[8]= {-1, -1, -1, 0, 1, 1, 1, 0};
int dj[8]= {-1, 0, 1, 1, 1, 0, -1, -1};

char s[101];
bool valid(struct celula nod)
{
    if(nod.lin>=0 && nod.lin<n && nod.col>=0 && nod.col<m)
        return 1;
    return 0;
}

void bfs(struct celula start, int d[101][101])
{
    int vecin_x;
    int vecin_y;
    coada.push(start);
    d[start.lin][start.col]=0;
    struct celula nod;
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        for(int k=0; k<8; k++)
        {
            vecin_x= nod.lin+ di[k];
            vecin_y=nod.col+ dj[k];
            struct celula vecin= celula(vecin_x, vecin_y);
            if(valid(vecin)==1 && d[vecin.lin][vecin.col]!=-2)
            {
                if(d[vecin.lin][vecin.col]==-1  || d[vecin.lin][vecin.col]>1+ d[nod.lin][nod.col] )
                {
                    d[vecin.lin][vecin.col]=1 + d[nod.lin][nod.col];
                    coada.push(vecin);
                }
            }
        }
    }
}
int main()
{
    int nr[101][101];
    int nj[101][101];

    int i,j;
    struct celula start_r, start_j;
    in>>n>>m;
    in.get();
    for( i=0; i<n; i++)
    {
        in.getline(s,101);


        for( j=0; j<=strlen(s)-1; j++)
        {

            if(s[j]=='R')
            {
                nr[i][j]=0;
                nj[i][j]=-1;
                start_r=celula(i,j);
            }
            else if(s[j]=='J')
            {
                nj[i][j]=0;
                nr[i][j]=-1;
                start_j=celula(i,j);

            }
            else if(s[j]==' ')
            {
                nj[i][j]=-1;
                nr[i][j]=-1;
            }
            else if(s[j]=='X')
            {
                nj[i][j]=-2;
                nr[i][j]=-2;
            }

        }

        for(int k= strlen(s) ; k<m; k++)
        {
            nj[i][j]=-1;
            nr[i][j]=-1;
        }


    }
    bfs(start_r, nr);
    bfs(start_j, nj);
    int dmin=-1;
    struct celula pos;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            if(nr[i][j]==nj[i][j] && nr[i][j]>=0)
            {
                if (dmin==-1)
                {
                    dmin=nr[i][j];
                    pos=celula(i,j);

                }
                else if(nr[i][j]<dmin)
                {
                    dmin=nr[i][j];
                    pos=celula(i,j);

                }

            }

    }
    out<<dmin+1<<" "<<pos.lin+1<<" "<<pos.col+1;

    return 0;
}