Cod sursa(job #2216029)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 24 iunie 2018 16:35:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=1e2, MMAX=1e2;

char rand_nou, caracter;

struct punct
{
    int x, y;
};

punct Q[NMAX*MMAX+3];

int R[NMAX+2][MMAX+2], J[NMAX+2][MMAX+2];

int N, M, i, j, t, p, u;
int x, y, xx, yy;

int dx[8]= {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8]= {0, 1, 1, 1, 0, -1, -1, -1};

int X1, Y1, X2, Y2;

bool ok;

int main()
{
    f>>N>>M;

    f.get(rand_nou);

    for(i=1; i<=N; i++)
    {
        ok=false;

        for(j=1; j<=M; j++)
        {
            f.get(caracter);

            if(caracter=='\n' && j==M)
                ok=true;

            if(caracter=='X')
                R[i][j]=J[i][j]=-1;

            else if(caracter=='R')
            {
                X1=i;
                Y1=j;
            }

            else if(caracter=='J')
            {
                X2=i;
                Y2=j;
            }
        }

        if(ok==false)
            f.get(rand_nou);
    }

    //Romeo
    p=u=1;

    Q[1].x=X1;
    Q[1].y=Y1;

    R[X1][Y1]=1;

    while(p<=u)
    {
        x=Q[p].x;
        y=Q[p].y;

        for(t=0; t<8; t++)
        {
            xx=x+dx[t];
            yy=y+dy[t];

            if(R[xx][yy]==0 && 1<=xx && xx<=N && 1<=yy && yy<=M)
            {
                R[xx][yy]=R[x][y]+1;

                u++;
                Q[u].x=xx;
                Q[u].y=yy;
            }
        }

        p++;
    }

    //Julieta
    p=u=1;

    Q[1].x=X2;
    Q[1].y=Y2;

    J[X2][Y2]=1;

    while(p<=u)
    {
        x=Q[p].x;
        y=Q[p].y;

        for(t=0; t<8; t++)
        {
            xx=x+dx[t];
            yy=y+dy[t];

            if(J[xx][yy]==0 && 1<=xx && xx<=N && 1<=yy && yy<=M)
            {
                J[xx][yy]=J[x][y]+1;

                u++;
                Q[u].x=xx;
                Q[u].y=yy;
            }
        }

        p++;
    }

    int Min=INT_MAX;

    int sol_x=0, sol_y=0;

    for(i=1; i<=N; i++)
        for(j=1; j<=M; j++)
            if(R[i][j]==J[i][j] && R[i][j]>0)
            {
                if(R[i][j]<Min)
                {
                    Min=R[i][j];
                    sol_x=i;
                    sol_y=j;
                }
            }

    g<<Min<<' '<<sol_x<<' '<<sol_y<<'\n';

    return 0;
}