Cod sursa(job #1880532)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 15 februarie 2017 20:13:15
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.38 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");
int x[105][105]={0};
int z[105][105]={0};
int n,m,sti=105,stj=105,spi=105,spj=105;

int dl[8]= {-1,1,1,-1,0,1,0,-1};
int dc[8]= {1,1,-1,-1,1,0,-1,0};

int l;

char v[105][105];

void verif(int i,int j)
{
    if (v[i][j]=='R')
    {
        sti=i;
        stj=j;
    }
    else if (v[i][j]=='J')
    {
        spi=i;
        spj=j;
    }
    if (sti!=105&&spi!=105)
        return;
    if (j==m)
        verif(i+1,0);
    else
        verif(i,j+1);


}


void Lee1()
{

    queue < pair < int, int > > coada;
    coada.push(make_pair(sti,stj));
    while (1)
    {
        int i=coada.front().first;
        int j=coada.front().second;
        coada.pop();
        for (int k=0; k<4; k++)
        {
            int iu=i+dl[k];
            int ju=j+dc[k];


            if (v[iu][ju]==' '||v[iu][ju]=='J')
            {
                if (x[iu][ju]==0)
                {

                    if (k==0)
                    {
                        if (v[iu][ju-1]==' '&&v[iu+1][ju]==' ')
                        {
                            x[iu][ju]=x[i][j]+1;
                            coada.push(make_pair(iu,ju));
                        }
                    }
                    else if (k==1)
                    {
                        if (v[iu-1][ju]==' '&&v[iu][ju-1]==' ')
                        {
                            x[iu][ju]=x[i][j]+1;
                            coada.push(make_pair(iu,ju));
                        }
                    }
                    else if (k==2)
                    {
                        if (v[iu][ju+1]==' '&&v[iu-1][ju]==' ')
                        {
                            x[iu][ju]=x[i][j]+1;
                            coada.push(make_pair(iu,ju));
                        }
                    }
                    else if (k==3)
                    {
                        if (v[iu][ju+1]==' '&&v[iu+1][ju]==' ')
                        {
                            x[iu][ju]=x[i][j]+1;
                            coada.push(make_pair(iu,ju));
                        }
                    }
                }

            }
            if (v[iu][ju]=='J'&&x[iu][ju])
            {
                l=ceil(x[iu][ju]+1)/2;
                return;
            }
        }
        for (int k=4; k<8; k++)
        {

            int iu=i+dl[k];
            int ju=j+dc[k];
            if (v[iu][ju]==' '||v[iu][ju]=='J')
            {
                if (x[iu][ju]==0)
                {
                    x[iu][ju]=x[i][j]+1;
                    coada.push(make_pair(iu,ju));
                }
            }
            if (v[iu][ju]=='J'&&x[iu][ju])
            {
                l=ceil(x[iu][ju]+1)/2;
                return;
            }

        }
    }
}

void Lee2()
{

    queue < pair < int,int > > coada2;
    coada2.push(make_pair(spi,spj));
    while (1)
    {
        int i=coada2.front().first;
        int j=coada2.front().second;
        coada2.pop();
        for (int k=0; k<4; k++)
        {
            int iu=i+dl[k];
            int ju=j+dc[k];
            if (v[iu][ju]==' ')
            {
                if (z[iu][ju]==0)
                {

                    if (k==0)
                    {
                        if (v[iu][ju-1]==' '&&v[iu+1][ju]==' ')
                        {
                            z[iu][ju]=z[i][j]+1;
                            coada2.push(make_pair(iu,ju));
                        }
                    }
                    else if (k==1)
                    {
                        if (v[iu-1][ju]==' '&&v[iu][ju-1]==' ')
                        {
                            z[iu][ju]=z[i][j]+1;
                            coada2.push(make_pair(iu,ju));
                        }
                    }
                    else if (k==2)
                    {
                        if (v[iu][ju+1]==' '&&v[iu-1][ju]==' ')
                        {
                            z[iu][ju]=z[i][j]+1;
                            coada2.push(make_pair(iu,ju));
                        }
                    }
                    else if (k==3)
                    {
                        if (v[iu][ju+1]==' '&&v[iu+1][ju]==' ')
                        {
                            z[iu][ju]=z[i][j]+1;
                            coada2.push(make_pair(iu,ju));
                        }
                    }
                }

            }
        if (z[iu][ju]==x[iu][ju]&&x[iu][ju]==l)
            {g<<iu+1<<' '<<ju+1<<' '<<l+1;
            return;}
        }
        for (int k=4; k<8; k++)
        {

            int iu=i+dl[k];
            int ju=j+dc[k];
            if (v[iu][ju]==' ')
            {
                if (z[iu][ju]==0)
                {
                    z[iu][ju]=z[i][j]+1;
                    coada2.push(make_pair(iu,ju));
                }
            }


        if (z[iu][ju]==x[iu][ju]&&x[iu][ju]==l)
            {g<<iu+1<<' '<<ju+1<<' '<<l+1;
            return;}
        }
    }
}


int main()
{
    int i;
    f>>n>>m;
    f.get();
    for (i=0; i<n; i++)
        f.getline(v[i],m+1);
    verif(0,0);
    Lee1();
    Lee2();


    return 0;
}