Cod sursa(job #2165118)

Utilizator bogdanbenteaBentea Bogdan bogdanbentea Data 13 martie 2018 11:12:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");

char ch[102];
int n,m,i,j,prim,ultim,clin[100002],ccol[100002];
int pl,pc,vl,vc,is,js,ib,jb,a[101][101],b[101][101],k,mn=2000000000;
int dl[]={-1,-1,-1,0,1,1, 1, 0};
int dc[]={-1, 0, 1,1,1,0,-1,-1};

int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin.get();
        cin.get(ch,102);
        for(j=0;j<m;j++)
        {
            if(ch[j]=='R')
            {
                is=i;
                js=j+1;
            }
            else
            {
                if(ch[j]=='J')
                {
                    ib=i;
                    jb=j+1;
                }
                else
                {
                    if(ch[j]=='X')
                        a[i][j+1]=b[i][j+1]=-1;
                }
            }
        }
    }
    /**
    cout<<"ROMEO: "<<is<<" "<<js;
    cout<<"JULIETA: "<<ib<<" "<<jb;
    cout<<'\n';
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
        cout<<'\n';
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<b[i][j]<<" ";
        cout<<'\n';
    }
    **/

    ///bordare
    for(j=0;j<=m+1;j++)
        a[0][j]=a[n+1][j]=b[0][j]=b[n+1][j]-1;
    for(i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=b[i][0]=b[i][m+1]=-1;

    ///ROMEO
    prim=1;
    ultim=1;
    clin[1]=is;
    ccol[1]=js;
    a[is][js]=1;
    while(prim<=ultim)
    {
        pl=clin[prim];
        pc=ccol[prim];

        for(k=0;k<8;k++)
        {
            vl=pl+dl[k];
            vc=pc+dc[k];
            if(a[vl][vc]==0)
            {
                a[vl][vc]=a[pl][pc]+1;
                ultim++;
                clin[ultim]=vl;
                ccol[ultim]=vc;
            }
        }
        prim++;
    }
    /**
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
        cout<<'\n';
    }
    **/

    ///JULIETA
    int lin=102,col=102;
    prim=1;
    ultim=1;
    clin[1]=ib;
    ccol[1]=jb;
    b[ib][jb]=1;
    while(prim<=ultim)
    {
        pl=clin[prim];
        pc=ccol[prim];

        for(k=0;k<8;k++)
        {
            vl=pl+dl[k];
            vc=pc+dc[k];
            if(b[vl][vc]==0)
            {
                b[vl][vc]=b[pl][pc]+1;
                ultim++;
                clin[ultim]=vl;
                ccol[ultim]=vc;
                if(a[vl][vc]==b[vl][vc])
                {
                    if(a[vl][vc]<mn)
                    {
                        mn=a[vl][vc];
                        lin=vl;
                        col=vc;
                    }
                    else
                    {
                        if(a[vl][vc]==mn)
                        {
                            if(lin>vl)
                            {
                                lin=vl;
                                col=vc;
                            }
                            else
                                if(vl==lin && col>vc)
                                {
                                    lin=vl;
                                    col=vc;
                                }
                        }
                    }
                }
            }
        }
        prim++;
    }

    /**
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<b[i][j]<<" ";
        cout<<'\n';
    }
    **/

    cout<<mn<<" "<<lin<<" "<<col;
    return 0;
}