Cod sursa(job #2180817)

Utilizator alexkosaAlex Kosa alexkosa Data 21 martie 2018 11:07:18
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int n,m,a[103][103],ifin,jfin,timp,i1,i2,j1,j2,b[103][103];
queue<pair<int,int> >coada;

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

bool verif(int i,int j)
{
    if(i<1 || j<1 || i>n || j>m)
        return false;
    return true;
}
void lee()
{
    int iurm,jurm,i,j;
    coada.push(make_pair(i1,j1));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(int k=0;k<8;k++)
        {
            iurm=i+dx[k];
            jurm=j+dy[k];
            if(verif(iurm,jurm) && a[iurm][jurm]==0)
            {
                coada.push(make_pair(iurm,jurm));
                a[iurm][jurm]=a[i][j]+1;
            }
        }
    }

}

void lee2()
{
    int i,j,iurm,jurm;
    coada.push(make_pair(i2,j2));
    int ok=1;
    while(!coada.empty() && ok)
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(int k=0;k<8;k++)
        {
            iurm=i+dx[k];
            jurm=j+dy[k];
            if(a[i2][j2]%2==0)
            {
                if(b[i][j]+1==a[iurm][jurm])
                {ifin=iurm;
                jfin=jurm;
                timp=a[iurm][jurm];
                ok=0;
                break;
                }
            }
            if(a[i2][j2]%2==1)
            {
                if(b[i][j]==a[iurm][jurm])
                {
                    timp=b[i][j]+1;
                    if(i<iurm)
                    {
                        ifin=i;
                        jfin=j;
                    }
                    else if(iurm<i)
                    {
                        ifin=iurm;
                        jfin=jurm;
                    }
                    else if(iurm==i)
                    {
                        ifin=i;
                        if(j<jurm)
                            jfin=j;
                        else
                            jfin=jurm;
                    }
                    ok=0;
                    break;
                }
            }
            if(verif(iurm,jurm) && b[iurm][jurm]==0 && a[iurm][jurm]>0)
            {
                b[iurm][jurm]=b[i][j]+1;
                coada.push(make_pair(iurm,jurm));
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    fin.get();
    char s[103];
    int ok1=1,ok2=1;
    for(int i=1;i<=n;i++)
    {
        fin.getline(s,103);
        for(int j=0;j<m;j++)
        {
            if(s[j]=='R' && ok1)
            {
                i1=i;
                j1=j+1;
                ok1=0;
            }
            if(s[j]=='J' && ok2)
            {
                i2=i;
                j2=j+1;
                ok2=0;
            }
            if(s[j]=='X')
                {a[i][j+1]=-1;
                b[i][j+1]=-1;}
        }
    }


    lee();
    lee2();
    timp++;
    fout<<timp<<" "<<ifin<<" "<<jfin;

}