Cod sursa(job #2519828)

Utilizator NoemikulcsarKulcsar Noemi Noemikulcsar Data 8 ianuarie 2020 14:46:53
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int n,m,A,B,C;
int rx,ry,jx,jy;
bool ok;
int di[]={1,-1,0,0,1,1,-1,-1};
int dj[]={0,0,1,-1,-1,1,-1,1};
int a[101][101],b[101][101];
char c[101];
queue < pair < int, int > > coada;

void Read()
{
    in>>n>>m;
    in.getline(c, 101);
    for(int i=0;i<n;i++)
    {
        in.getline(c, 101);
        for(int j=0;j<m;j++)
        {
            if(c[j]=='X') a[i][j]=b[i][j]=-1;
            if(c[j]=='R')
            {
                rx=i;
                ry=j;
            }
            if(c[j]=='J')
            {
                jx=i;
                jy=j;
            }
        }
    }
}

int OK(int i, int j)
{
    if(i<0 || j<0 || i>=n || j>=m) return 0;
    if(a[i][j]=='-1') return 0;
    return 1;
}

void LeeR()
{
    int i,j,i_urmator,j_urmator;
    a[rx][ry]=1;
    coada.push(make_pair(rx, ry));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(int d=0;d<8;d++)
        {
            i_urmator=i+di[d];
            j_urmator=j+dj[d];
            if(OK(i_urmator,j_urmator) && a[i_urmator][j_urmator]==0)
            {
                a[i_urmator][j_urmator]=a[i][j]+1;
                coada.push(make_pair(i_urmator,j_urmator));
            }
        }
    }
}

void LeeJ()
{
    int i,j,i_urmator,j_urmator;
    b[jx][jy]=1;
    coada.push(make_pair(jx, jy));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(int d=0;d<8;d++)
        {
            i_urmator=i+di[d];
            j_urmator=j+dj[d];
            if(OK(i_urmator,j_urmator) && b[i_urmator][j_urmator]==0)
            {
                b[i_urmator][j_urmator]=b[i][j]+1;
                coada.push(make_pair(i_urmator,j_urmator));
            }
        }
    }
}

int main()
{
    Read();
    LeeR();
    LeeJ();
    A=100000;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i][j]==b[i][j] && a[i][j]>0 && A>a[i][j])
            {
                ok=1;
                A=a[i][j];
                B=i+1;
                C=j+1;
            }
    if(ok) out<<A<<" "<<B<<" "<<C;
    else
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                for(int d=0;d<8;d++)
                {
                    if(OK(i+di[d],j+dj[d]) && a[i][j]==b[i+di[d]][j+dj[d]] && a[i][j]>0 && A>a[i][j])
                    {
                        A=a[i][j]+1;
                        B=i+1;
                        C=j+1;
                        ok=1;
                    }
                }
        out<<A<<" "<<B<<" "<<C;
    }
    return 0;
}