Cod sursa(job #2340964)

Utilizator belacPhitz Me belac Data 11 februarie 2019 13:11:44
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

int n,m,i,j,si,sj,fi,fj;
int a[101][101],b[101][101];
char s[256];

int di[]= {0,0,1,-1,1,-1,-1,1};
int dj[]= {1,-1,0,0,1,-1,1,-1};

queue <pair <int,int > >coada;

void read()
{
    f>>n>>m;
    for(i=0; i<=n; i++)
    {
        f.getline(s,256);
        for(j=1; j<=m; j++)
        {
            char x=s[j-1];
            if(x=='X')
            {
                a[i][j]=-1;
                b[i][j]=-1;
            }
            if(x=='R')
            {
                si=i;
                sj=j;
            }
            if(x=='J')
            {
                fi=i;
                fj=j;
            }
            if(x==' ')
            {
                a[i][j]=0;
                b[i][j]=0;
            }
        }
    }
}

bool oka(int i,int j)
{
    if(i<1||i>n||j<1||j>m)
        return false;
    if(a[i][j]==-1)
        return false;
    return true;
}

void Leea()
{
    int iur,jur,k;
    a[si][sj]=1;
    coada.push(make_pair(si,sj));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(k=0; k<8; k++)
        {
            iur=i+di[k];
            jur=j+dj[k];
            if(oka(iur,jur)&&a[iur][jur]==0)
            {
                a[iur][jur]=a[i][j]+1;
                coada.push(make_pair(iur,jur));
            }
        }
    }
}

void Leeb()
{
    int iur,jur,k;
    b[fi][fj]=1;
    coada.push(make_pair(fi,fj));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(k=0; k<8; k++)
        {
            iur=i+di[k];
            jur=j+dj[k];
            if(oka(iur,jur)&&b[iur][jur]==0)
            {
                b[iur][jur]=b[i][j]+1;
                coada.push(make_pair(iur,jur));
            }
        }
    }
}
/*
void afisare()
{
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
            cout<<b[i][j]<<" ";
        cout<<'\n';
    }
    cout<<'\n';
}
*/
/*
afisare();
cout<<si<<" "<<sj<<" "<<fi<<" "<<fj;
*/
int main()
{
    int x=0,y=0;
    read();
    Leea();
    Leeb();
    int minim=10000001;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(a[i][j]==b[i][j]&&a[i][j]>0&&a[i][j]<minim)
            {
                minim=a[i][j];
                x=i;
                y=j;
            }
        }
    }
    g<<minim<<" "<<x<<" "<<y;

    return 0;
}