Cod sursa(job #1824669)

Utilizator vlad2004SuntUnNanoTub vlad2004 Data 8 decembrie 2016 11:12:24
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <fstream>
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
const int nmax=100;
int v[nmax+2][nmax+2];

int qx[nmax*nmax+1],qy[nmax*nmax+1];

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


int main()
{
    int n,m;
    in>>n>>m;
    string s;
    //getline(in,s);
    int qb=1 , qe=2;
    for(int i = 1; i <= n; i++)
    {
        getline(in,s);
        for(int j=1; j <= m; j++)
        {
            if(s[j-1]=='R')
            {
                v[i][j]=1;
                qx[1]=i;
                qy[1]=j;

            }
            if(s[j-1]=='J')
            {
                v[i][j]=nmax*nmax+1;
                qx[2]=i;
                qy[2]=j;
            }
            if(s[j-1]=='X')
                v[i][j]=-1;

        }
    }
    for(int i=0; i<=n+1; i++)
    {
        v[i][0]=-1;
        v[i][m+1]=-1;
    }
    for(int i=0; i<=m+1; i++)
    {
        v[0][i]=-1;
        v[n+1][i]=-1;
    }
    int sol=nmax*nmax+1,solx=0,soly=0;
    while(qb<=qe)
    {
        int x,y;
        x=qx[qb];
        y=qy[qb];
        qb++;
        for(int i=0; i<4; i++)
        {
            int xn,yn;
            xn=x+dx[i];
            yn=y+dy[i];
            if(v[xn][yn]==0)
            {
                qe++;
                v[xn][yn]=v[x][y]+1;
                qx[qe]=xn;
                qy[qe]=yn;
            }
            if (v[xn][yn]!=0 && v[xn][yn]!=-1) {
                if( (v[x][y]<nmax*nmax && v[xn][yn]>nmax*nmax)||
                    (v[x][y]>nmax*nmax && v[xn][yn]<nmax*nmax)  )
                {
                    int a=v[x][y],b=v[xn][yn];
                    if(a>b)
                    {
                        a=a-nmax*nmax;
                    }
                    else
                    {
                        b=b-nmax*nmax;
                    }
                    if(a+1>=b)
                    {
                        if(sol>a+1 ||
                            (sol==a+1 && solx>xn) ||
                            (sol==a+1 && solx==xn && soly>yn))
                        {
                            sol=a+1;
                            solx=xn;
                            soly=yn;
                        }

                    }
                    if(b>=a+1)
                    {
                        if(sol>b ||
                            (sol==b && solx>xn) ||
                            (sol==b && solx==xn && soly>yn))
                        {
                            sol=b;
                            solx=xn;
                            soly=yn;
                        }
                    }
                    if(a>=b+1)
                    {
                        if(sol>a||
                           (sol==a && solx>x) ||
                           (sol==a && solx==x && soly>y))
                        {
                            sol=a;
                            solx=x;
                            soly=y;
                        }
                    }
                    if(b+1>=a)
                    {
                        if(sol>b+1 ||
                            (sol==b+1 && solx>x)||
                            (sol==b+1 && solx==x && soly>y))
                        {
                            sol=b+1;
                            solx=x;
                            soly=y;
                        }
                    }
                }
            }
        }
    }
    out<<sol-1<<" "<<solx<<" "<<soly<<'\n';
    return 0;
}