Cod sursa(job #2159247)

Utilizator andreipredaAndrei Preda andreipreda Data 10 martie 2018 20:29:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <bits/stdc++.h>

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

queue <pair<int,int> >coada;

int n,m,i,j,xi,yi,xf,yf;
int MapR[101][101],MapJ[101][101],went[101][101];
int dx[]={-1,-1,1,1,0,1,-1,0};
int dy[]={0,1,0,1,1,-1,-1,-1};

void citire()
{
    char sir[256];
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin.get();
        fin.get(sir,sizeof(sir));
        for(j=0;j<strlen(sir);j++)
        {
            if(sir[j]=='X')
            {
                MapR[i][j+1]=-1;
                MapJ[i][j+1]=-1;
            }
            else if(sir[j]=='R')
            {
                xi=i;
                yi=j+1;
                MapR[i][j+1]=0;
                MapJ[i][j+1]=0;
            }
            else if(sir[j]=='J')
            {
                xf=i;
                yf=j+1;
                MapR[i][j+1]=0;
                MapJ[i][j+1]=0;
            }
            else{
                MapR[i][j+1]=0;
                MapJ[i][j+1]=0;
            }
        }
    }
}

void afisare(int Map[101][101])
{
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            fout<<setw(3)<<Map[i][j];
        }
        fout<<endl;
    }
}

bool ok(int i,int j,int Map[101][101])
{
    if(i<1 || j<1 || i>n || j>m)
        return false;
    if(Map[i][j]!=0)
        return false;
    return true;
}

void mod()
{
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            went[i][j]=false;
        }
    }
}

void lee(int xi,int yi,int xf,int yf,int Map[101][101])
{
    int i,j,inext,jnext;
    Map[xi][yi]=1;
    coada.push(make_pair(xi,yi));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(int k=0;k<8;k++)
        {
            inext=i+dx[k];
            jnext=j+dy[k];
            if(ok(inext,jnext,Map)==true && went[inext][jnext]==false)
            {
                coada.push(make_pair(inext,jnext));
                Map[inext][jnext]=Map[i][j]+1;
                went[inext][jnext]=true;
            }
        }
    }
    mod();
}

int main()
{
    int tmin=n*m+5;
    int p=-1,q=-1;
    citire();
    lee(xi,yi,xf,yf,MapR);
    lee(xf,yf,xi,yi,MapJ);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(MapR[i][j]==MapJ[i][j])
            {
                if(MapR[i][j]!=-1  && MapR[i][j]!=0)
                {
                    if(MapR[i][j]<tmin)
                    {
                        tmin=MapR[i][j];
                        p=i;
                        q=j;
                    }
                }
            }
        }
    }
    fout<<tmin<<' '<<p<<' '<<q;
    //afisare(MapR);
    //fout<<endl;
    //afisare(MapJ);
    return 0;
}