Cod sursa(job #2712912)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 26 februarie 2021 19:48:40
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct Nod
{
    int x;
    int y;
};

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

int n,m,x_r,y_r,x_j,y_j,poz_x,poz_y;
int mat_r[105][105],mat_j[105][105],mini=100000000;

void bordare(int n, int m)
{
    for(int i=0; i<=n+1; i++)
    {
        mat_r[i][0]=-1;
        mat_r[i][m+1]=-1;
        mat_j[i][0]=-1;
        mat_j[i][m+1]=-1;
    }
    for(int j=0; j<=m+1; j++)
    {
        mat_r[0][j]=-1;
        mat_r[n+1][j]=-1;
        mat_j[0][j]=-1;
        mat_j[n+1][j]=-1;
    }
}

int x[4]= {1,-1,0,0};
int y[4]= {0,0,1,-1};


void lee_r()
{
    queue<Nod>q;
    Nod w;
    w.x=x_r;
    w.y=y_r;
    q.push(w);
    while(!q.empty())
    {
        Nod nod;
        nod=q.front();
        q.pop();
        if(nod.x == x_j && nod.y == y_j)
        {
            return;
        }
        for(int i=0; i<4; i++)
        {
            if( mat_r[nod.x + x[i]][nod.y + y[i]]==0)
            {
                Nod add;
                add.x = nod.x + x[i];
                add.y = nod.y + y[i];
                mat_r[nod.x+ x[i]][nod.y+ y[i]]=mat_r[nod.x][nod.y]+1;
                q.push(add);
            }
        }
    }
}

void lee_j()
{
    queue<Nod>q;
    Nod w;
    w.x=x_j;
    w.y=y_j;
    q.push(w);
    while(!q.empty())
    {
        Nod nod;
        nod=q.front();
        q.pop();
       // cout<<nod.x<<" "<<nod.y<<" \n";
       // cout<<mat_j[nod.x][nod.y]<<" "<<mat_r[nod.x][nod.y]<<"\n\n";
         if(nod.x == x_r && nod.y == y_r)
        {
            return;
        }

        if(mat_j[nod.x][nod.y]==mat_r[nod.x][nod.y])
        {
            if(mini>mat_j[nod.x][nod.y])
            {
                mini=mat_j[nod.x][nod.y];
                poz_x=nod.x;
                poz_y=nod.y;
            }

        }
        for(int i=0; i<4; i++)
        {
            if( mat_j[nod.x + x[i]][nod.y + y[i]]==0)
            {
                Nod add;
                add.x = nod.x + x[i];
                add.y = nod.y + y[i];
                mat_j[nod.x+ x[i]][nod.y+ y[i]]=mat_j[nod.x][nod.y]+1;
                q.push(add);
            }
        }

    }
}


int main()
{

    in>>n>>m;
    char c,p[105];
    in.getline(p,104);
    for(int i=1; i<=n; i++)
    {
        in.getline(p,104);
        for(int j=1; j<=m; j++)
        {
            c=p[j-1];
            if(c=='X')
            {
                mat_r[i][j]=-1;
                mat_j[i][j]=-1;
            }
            else if(c=='R')
            {
                x_r=i;
                y_r=j;
                mat_r[i][j]=1;
            }
            else if(c=='J')
            {
                x_j=i;
                y_j=j;
                mat_j[i][j]=1;
            }
        }
    }
    bordare(n,m);
    lee_r();
    lee_j();
    out<<mini-1<<" "<<poz_x<<" "<<poz_y;
    return 0;
}