Cod sursa(job #2049788)

Utilizator Luca19Hritcu Luca Luca19 Data 27 octombrie 2017 17:28:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include<fstream>

using namespace std;

 ifstream fin("rj.in");
 ofstream fout("rj.out");
int a[105][105],mat[105][105],L,C,xr,yr,xj,yj;

short dx[] = {-1,-1,-1, 0, 1, 1, 1, 0};

short dy[] = {-1, 0, 1, 1, 1, 0,-1,-1};

struct coord
{
    int x,y;
};

coord q[10000];

void Citire()
{
    int i,j;
    char s[110];


    fin>>L>>C;
    fin.get();

    for(i=1; i<=L; i++)
    {
        fin.getline(s,110);
        for(j=0; j<C; j++)

            if(s[j]==' ')   a[i][j+1] = 0;
            else if(s[j]=='X')  a[i][j+1] = 1;
                else if(s[j]=='R')  {   xr = i; yr = j+1; }
                    else    {   xj = i; yj = j+1;   }
    }

    fin.close();

    for(i=1; i<=L; i++)
        for(j=1; j<=C; j++)
            mat[i][j] = a[i][j];
}
void Bordare()
{
    int i,n,m;

    n = L + 1;
    m = C + 1;

    for(i=0; i<=n; i++)
        mat[i][0] = mat[i][m] = a[i][0] = a[i][m] = -1;

    for(i=0; i<=m; i++)
        mat[0][i] = mat[n][i] = a[0][i] = a[n][i] = -1;
}

void Romeo()
{
    int pr,ul,i,j,x,y,k;
    pr = ul = 0;

    a[xr][yr] = 2;
    q[ul].x = xr;
    q[ul].y = yr;

    while(pr<=ul)
    {
        i = q[pr].x;
        j = q[pr].y;
        pr++;
        for(k=0; k<8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];

            if(a[x][y] == 0)
            {
                ul++;
                q[ul].x = x;
                q[ul].y = y;
                a[x][y] = a[i][j] + 1;
            }
        }
    }
}
void Julieta()
{
    int pr,ul,i,j,x,y,k;
    pr = ul = 0;

    mat[xj][yj] = 2;
    q[ul].x = xj;
    q[ul].y = yj;

    while(pr<=ul)
    {
        i = q[pr].x;
        j = q[pr].y;
        pr++;
        for(k=0; k<8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if(mat[x][y] == 0)
            {
                ul++;
                q[ul].x = x;
                q[ul].y = y;
                mat[x][y] = mat[i][j] + 1;
            }
        }
    }
}

void Afisare()
{
    int i,j,lin=0,col=0,tmin=1000000;

    for(i=1; i<=L; i++)
        for(j=1; j<=C; j++)
        {
            if(a[i][j] == mat[i][j] && a[i][j] > 1)
            {
                if(a[i][j] - 1 < tmin)
                {
                    tmin = a[i][j] - 1;
                    lin = i;
                    col = j;
                }
            }
        }



    fout<<tmin<<" "<<lin<<" "<<col<<"\n";

    fout.close();
}

int main ()
{
    Citire();
    Bordare();
    Romeo();
    Julieta();
    Afisare();
    return 0;
}