Cod sursa(job #2356555)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 26 februarie 2019 19:34:33
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int n,m,i,j;
int poz1_romeo,poz2_romeo,poz1_julieta,poz2_julieta;
int poz1,poz2,rez=10000000;
char x[105];
int a[105][105],b[105][105];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

void romeo()
{
    int drum1[10001];
    int drum2[10001];
    int p,q;
    int i=1,k=1,j;
    drum1[1]=poz1_romeo;
    drum2[1]=poz2_romeo;
    while (i<=k)
    {
        p=drum1[i];
        q=drum2[i];
        for (j=0;j<=7;j++)
            if (a[p+dx[j]][q+dy[j]]==0)
            {
                k++;
                drum1[k]=p+dx[j];
                drum2[k]=q+dy[j];
                a[p+dx[j]][q+dy[j]]=a[p][q]+1;
            }
        i++;
    }
}

void julieta()
{
    int drum1[10001];
    int drum2[10001];
    int p,q;
    int i=1,k=1,j;
    drum1[1]=poz1_julieta;
    drum2[1]=poz2_julieta;
    while (i<=k)
    {
        p=drum1[i];
        q=drum2[i];
        for (j=0;j<=7;j++)
            if (b[p+dx[j]][q+dy[j]]==0)
            {
                k++;
                drum1[k]=p+dx[j];
                drum2[k]=q+dy[j];
                b[p+dx[j]][q+dy[j]]=b[p][q]+1;
                if (a[p+dx[j]][q+dy[j]]==b[p+dx[j]][q+dy[j]] && b[p+dx[j]][q+dy[j]]<rez)
                {
                    rez=b[p+dx[j]][q+dy[j]];
                    poz1=p+dx[j];
                    poz2=q+dy[j];
                }
                else
                    if (a[p+dx[j]][q+dy[j]]==b[p+dx[j]][q+dy[j]] && b[p+dx[j]][q+dy[j]]==rez && (p+dx[j]+q+dy[j]<poz1+poz2))
                    {
                        rez=b[p+dx[j]][q+dy[j]];
                        poz1=p+dx[j];
                        poz2=q+dy[j];
                    }
            }
        i++;
    }
}

int main()
{
    f>>n>>m;
    f.get();
    for (i=1;i<=n;i++)
    {
        f.getline(x,sizeof(x));
        for (j=0;j<m;j++)
        {
            if (x[j]=='X')
            {
                a[i][j+1]=2;
                b[i][j+1]=2;
            }
            else
                if (x[j]=='R')
                {
                    a[i][j+1]=1;
                    b[i][j+1]=1;
                    poz1_romeo=i;
                    poz2_romeo=j+1;
                }
                else
                    if (x[j]=='J')
                    {
                        a[i][j+1]=1;
                        b[i][j+1]=1;
                        poz1_julieta=i;
                        poz2_julieta=j+1;
                    }
        }
    }
    for (i=0;i<=n+1;i++)
    {
        a[i][0]=b[i][0]=-1;
        a[i][m+1]=b[i][m+1]=-1;
    }
    for (j=0;j<=m+1;j++)
    {
        a[0][j]=b[0][j]=-1;
        a[n+1][j]=b[n+1][j]=-1;
    }
    romeo();
    julieta();
    g<<rez<<" "<<poz1<<" "<<poz2;
    return 0;
}