Cod sursa(job #1346757)

Utilizator Tudordmdaniel marin Tudordm Data 18 februarie 2015 16:48:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<cstdio>

using namespace std;

int dlin[]= {-1,-1,0,1,1,1,0,-1};
int dcol[]= {0,-1,-1,-1,0,1,1,1};

int n,m;

int d1[102][102],d2[102][102];

char s[102][102];

struct poz
{

    int lin;
    int col;

};

poz q1[101*101],q2[101*101];

void Lee1(poz x0)
{

    poz x,y;
    int p=0,u=-1,i;
    q1[++u]=x0;
    d1[x0.lin][x0.col]=1;
    while(p<=u)
    {
        x=q1[p++];
        for(i=0; i<8; i++)
        {
            y.lin=x.lin+dlin[i];
            y.col=x.col+dcol[i];
            if(d1[y.lin][y.col]==0)
            {
                q1[++u]=y;
                d1[y.lin][y.col]=1+d1[x.lin][x.col];
            }
        }
    }
}
void Lee2(poz x0)
{

    poz x,y;
    int p=0,u=-1,i;
    q2[++u]=x0;
    d2[x0.lin][x0.col]=1;
    while(p<=u)
    {
        x=q2[p++];
        for(i=0; i<8; i++)
        {
            y.lin=x.lin+dlin[i];
            y.col=x.col+dcol[i];
            if(d2[y.lin][y.col]==0)
            {
                q2[++u]=y;
                d2[y.lin][y.col]=1+d2[x.lin][x.col];
            }
        }
    }
}

void bordare()
{

    int i,j;
    for(j=0; j<=m+1; j++)
        d1[0][j]=d1[n+1][j]=d2[0][j]=d2[n+1][j]=-1;
    for(i=0; i<=n+1; i++)
        d1[i][0]=d1[i][m+1]=d2[i][0]=d2[i][m+1]=-1;

}

poz start1,start2,sol;

int main()
{

    int minim=999999;

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

    scanf("%d%d\n",&n,&m);

    for(int i=1; i<=n; i++)
    {

        gets(1+s[i]);
        for(int j=1; j<=m; j++)
        {

            if(s[i][j]==' ')    d1[i][j]=d2[i][j]=0;

            else if(s[i][j]=='R')
            {

                start1.lin=i;
                start1.col=j;
                d1[i][j]=1;
            }
            else if(s[i][j]=='J')
            {

                start2.lin=i;
                start2.col=j;
                d2[i][j]=1;
            }
            else d1[i][j]=d2[i][j]=-1;
        }

    }

    bordare();


    Lee1(start1);
    Lee2(start2);

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {

            if(d1[i][j]==d2[i][j]&&d1[i][j]!=-1&&d1[i][j]!=0)
            {

                if(d1[i][j]<minim)
                {

                    minim=d1[i][j];
                    sol.lin=i;
                    sol.col=j;
                }
                else if(d1[i][j]==minim)
                {

                    if(i<sol.lin)
                    {
                        minim=d1[i][j];
                        sol.lin=i;
                        sol.col=j;
                    }
                    else if(i==sol.lin)
                    {
                        if(j<sol.col)
                        {
                            minim=d1[i][j];
                            sol.lin=i;
                            sol.col=j;
                        }
                    }
                }
            }
        }
    }

    printf("%d %d %d",minim,sol.lin,sol.col);

    return 0;
}