Cod sursa(job #1693686)

Utilizator zeeboBuzatu Vlad zeebo Data 23 aprilie 2016 18:07:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.17 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int main()
{
    int m,n,x1,y1,x2,y2,X,Y,P,l,cc,b[100][100],c[100][100],d[100][100],s,f;
    char a[100][100];
    y>>n>>m;
    struct
    {
        int x,y,p;
    } Q[1001];

    char str[101];
    y.getline(str,100);

    for (int i = 1; i <= n; i++)
    {
        y.getline(str,100);
        for (int j = 0; j < strlen(str); j++){

            if (str[j] == ' ')
                b[i][j+1] = 999,
                c[i][j+1] = 999;
            else
            if (str[j] == 'X')
                b[i][j+1] = -1,
                c[i][j+1] = -1;

            if (str[j]=='R')
                x1=i,y1=j+1;
            else
            if(str[j]=='J')
                x2=i,y2=j+1;
        }

        if (strlen(str) < m)
            for (int j = strlen(str)+1; j <=m; j++)
                b[i][j] = 999,
                c[i][j] = 999;
    }

//ROMEO
    Q[1].x=x1;
    Q[1].y=y1;
    Q[1].p=0;
    s=1;
    f=2;

    for(int p=1; p<=n; p++)
        for(int r=1; r<=m; r++)
            d[p][r]=0;

    while(s<=f)
    {
        X=Q[s].x;
        Y=Q[s].y;
        P=Q[s].p;

        if(b[X-1][Y]==999 && !d[X-1][Y])
        {
            Q[f].x=X-1;
            Q[f].y=Y;
            Q[f].p=P+1;
            d[X-1][Y]=1;
            f++;
        }

        if(b[X+1][Y]==999 && !d[X+1][Y])
        {
            Q[f].x=X+1;
            Q[f].y=Y;
            Q[f].p=P+1;
            d[X-1][Y]=1;
            f++;
        }

        if(b[X][Y-1]==999 && !d[X][Y-1])
        {
            Q[f].x=X;
            Q[f].y=Y-1;
            Q[f].p=P+1;
            d[X][Y-1]=1;
            f++;
        }


        if(b[X][Y+1]==999 && !d[X][Y+1])
        {
            Q[f].x=X;
            Q[f].y=Y+1;
            Q[f].p=P+1;
            d[X][Y+1]=1;
            f++;
        }

        if(b[X+1][Y+1]==999 && !d[X+1][Y+1])
        {
            Q[f].x=X+1;
            Q[f].y=Y+1;
            Q[f].p=P+1;
            d[X+1][Y+1]=1;
            f++;
        }
        if(b[X-1][Y-1]==999 && !d[X-1][Y-1])
        {
            Q[f].x=X-1;
            Q[f].y=Y-1;
            Q[f].p=P+1;
            d[X-1][Y-1]=1;
            f++;
        }
        if(b[X+1][Y-1]==999 && !d[X+1][Y-1])
        {
            Q[f].x=X+1;
            Q[f].y=Y-1;
            Q[f].p=P+1;
            d[X+1][Y-1]=1;
            f++;
        }
        if(b[X-1][Y+1]==999 && !d[X-1][Y+1])
        {
            Q[f].x=X-1;
            Q[f].y=Y+1;
            Q[f].p=P+1;
            d[X-1][Y+1]=1;
            f++;
        }
        s++;
    }

    for(int i=2; i<f; i++)
    {
        //if(  b[Q[i].x][Q[i].y] != -2 && b[Q[i].x][Q[i].y] !=  0 )
        if(Q[i].p < b[ Q[i].x ] [ Q[i].y ]) b[Q[i].x][Q[i].y]=Q[i].p;
    }

// JULIETA
    Q[1].x=x2;
    Q[1].y=y2;
    Q[1].p=0;
    s=1;
    f=2;
    for(int p=1; p<=n; p++)
        for(int r=1; r<=m; r++)
            d[p][r]=0;
    while(s<=f)
    {
        X=Q[s].x;
        Y=Q[s].y;
        P=Q[s].p;

        if(c[X-1][Y]==999 && !d[X-1][Y])
        {
            Q[f].x=X-1;
            Q[f].y=Y;
            Q[f].p=P+1;
            d[X-1][Y]=1;
            f++;
        }

        if(c[X+1][Y]==999  && !d[X+1][Y])
        {
            Q[f].x=X+1;
            Q[f].y=Y;
            Q[f].p=P+1;
            d[X+1][Y]=1;
            f++;
        }

        if(c[X][Y-1]==999 && !d[X][Y-1])
        {
            Q[f].x=X;
            Q[f].y=Y-1;
            Q[f].p=P+1;
            d[X][Y-1]=1;
            f++;
        }


        if(c[X][Y+1]==999 && !d[X][Y+1])
        {
            Q[f].x=X;
            Q[f].y=Y+1;
            Q[f].p=P+1;
            d[X][Y+1]=1;
            f++;
        }

        if(c[X+1][Y+1]==999 && !d[X+1][Y+1])
        {
            Q[f].x=X+1;
            Q[f].y=Y+1;
            Q[f].p=P+1;
            d[X+1][Y+1]=1;
            f++;
        }
        if(c[X-1][Y-1]==999 && !d[X-1][Y-1])
        {
            Q[f].x=X-1;
            Q[f].y=Y-1;
            Q[f].p=P+1;
            d[X-1][Y-1]=1;
            f++;
        }
        if(c[X+1][Y-1]==999 && !d[X+1][Y-1])
        {
            Q[f].x=X+1;
            Q[f].y=Y-1;
            Q[f].p=P+1;
            d[X+1][Y-1]=1;
            f++;
        }
        if(c[X-1][Y+1]==999 && !d[X-1][Y+1])
        {
            Q[f].x=X-1;
            Q[f].y=Y+1;
            Q[f].p=P+1;
            d[X-1][Y+1]=1;
            f++;
        }
        s++;
    }
    int mini=9999;
    for(int i=2; i<f; i++)
    {
        // if(  c[Q[i].x][Q[i].y] != -2 && c[Q[i].x][Q[i].y] !=  0 )
        if(Q[i].p < c[ Q[i].x ] [ Q[i].y ]) c[Q[i].x][Q[i].y]=Q[i].p;
    }

    mini = 999;
    int xi, yi;
    for (int i = 1; i<=n; i++)
        for (int j = 1; j <= m; j++)
            if (b[i][j] == c[i][j] && b[i][j] != -1 && b[i][j] != 999 && b[i][j] != 0){
                if (b[i][j] < mini)
                    mini = b[i][j],
                    xi = i,
                    yi = j;
            }


    w<<mini+1<<" "<<xi<<" "<<yi;
    return 0;
}