Cod sursa(job #1367677)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 2 martie 2015 00:20:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define dmax 110
#define Dmax 10010
using namespace std;

int N,M; char A[dmax]; int R[dmax][dmax]; int J[dmax][dmax];
struct COADA{int l,c,val;}C[Dmax];

int d_x[8]={-1,-1,0,1,1,1,0,-1};
int d_y[8]={0,1,1,1,0,-1,-1,-1};

void LEE_R(int x, int y)
{
    int p=1,u=1,x1,y1;

    C[p].l=x; C[p].c=y; C[p].val=1; R[x][y]=1;

    while(p<=u)
    {
        x=C[p].l; y=C[p].c;

        for(int i=0; i<8; i++)
        {
            x1=d_x[i]+x; y1=d_y[i]+y;

            if(R[x1][y1]>C[p].val+1 && x1>=1 && x1<=N && y1>=1 && y1<=M)
            {
                u++;
                C[u].l=x1; C[u].c=y1; C[u].val=C[p].val+1; R[x1][y1]=C[u].val;
            }
        }

        p++;
    }
}

void LEE_J(int x, int y)
{
    int p=1,u=1,x1,y1;

    C[p].l=x; C[p].c=y; C[p].val=1; J[x][y]=1;

    while(p<=u)
    {
        x=C[p].l; y=C[p].c;

        for(int i=0; i<8; i++)
        {
            x1=d_x[i]+x; y1=d_y[i]+y;

            if(J[x1][y1]>C[p].val+1 && x1>=1 && x1<=N && y1>=1 && y1<=M)
            {
                u++;
                C[u].l=x1; C[u].c=y1; C[u].val=C[p].val+1; J[x1][y1]=C[u].val;
            }
        }

        p++;
    }
}

int main()
{

    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    int i,j,x_R,y_R,x_J,y_J,T_min=Dmax,X,Y;

    scanf("%d%d",&N,&M); cin.get(); //TREC DE ENTER

    i=1;
    do
    {
    j=0;
    while(scanf("%c",&A[++j]) && A[j]!='\n')

        if(A[j]=='R') {R[i][j]=1; J[i][j]=N*M+1; x_R=i; y_R=j;}
        else
            if(A[j]=='J') {J[i][j]=1; R[i][j]=N*M+1; x_J=i; y_J=j;}
        else
            if(A[j]==' ') {R[i][j]=N*M+1; J[i][j]=N*M+1;}
        else
            if(A[j]=='X') {R[i][j]=-1; J[i][j]=-1;}

    for(int k=j; k<=M; k++) {R[i][k]=N*M+1; J[i][k]=N*M+1;}

    i++;
    }while(i<=N);

    LEE_R(x_R,y_R);

    /*for(i=1; i<=N; i++)
    {
        for(j=1; j<=M; j++) printf("%d ",R[i][j]); printf("\n");
    }
    printf("%d %d\n",x_R,y_R); printf("\n");*/

    LEE_J(x_J,y_J);

    /*for(i=1; i<=N; i++)
    {
        for(j=1; j<=M; j++) printf("%d ",J[i][j]); printf("\n");
    }
    printf("%d %d\n",x_J,y_J);*/

    for(i=1; i<=N; i++)
    {
        for(j=1; j<=M; j++)
        {
            if(R[i][j]==J[i][j] && R[i][j]!=-1 && R[i][j]!=N*M+1)
            {
                if(T_min>R[i][j]) {T_min=R[i][j]; X=i; Y=j;}
            }
        }
    }

    printf("%d %d %d",T_min,X,Y);

    return 0;
}