Cod sursa(job #2542519)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 10 februarie 2020 08:50:13
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m,aa,bb,cc;
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 citire()
{
    f>>n>>m;
    f.getline(c, 101);
    for(int i=0;i<n;i++) {
        f.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()
{
    citire();
    LeeR();
    LeeJ();
    aa=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 && aa>a[i][j])
            {
                ok=1;
                aa=a[i][j];
                bb=i+1;
                cc=j+1;
            }
    if(ok==1){
        g<<aa<<" "<<bb<<" "<<cc;
    }
    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 && aa>a[i][j])
                    {
                        aa=a[i][j]+1;
                        bb=i+1;
                        cc=j+1;
                        ok=1;
                    }
                }
        g<<aa<<" "<<bb<<" "<<cc;
    }
    return 0;
}