Cod sursa(job #1883213)

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

using namespace std;

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

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];
int x[105][105];
int z[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-1)
        verif(i+1,0);
    else
        verif(i,j+1);
}
void Lee()
{
    queue < pair < int, int > > coada;
    coada.push(make_pair(sti,stj));
    while (!coada.empty())
    {
        int i=coada.front().first;
        int j=coada.front().second;
        coada.pop();
        for (int k=0; k<8; k++)
        {
            int iu=i+dl[k];
            int ju=j+dc[k];
            if (x[iu][ju]==0)
                if (v[iu-1][ju-1]==' ')
                {
                    x[iu][ju]=x[i][j]+1;
                    coada.push(make_pair(iu,ju));
                }
        }

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



int main()
{
    int i;
    f>>n>>m;
    f.get();
    for (i=0; i<n; i++)
    {
        f.getline(v[i],m+1);
    }
    verif(0,0);
    sti++;stj++;spi++;spj++;
    for (i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            if (v[i-1][j-1]=='X')
            {
                x[i][j]=-1;
                z[i][j]=-1;
            }
            else if (v[i-1][j-1]==' ')
            {
                x[i][j]=0;
                z[i][j]=0;
            }
        }
    x[sti][stj]++;
    z[spi][spj]++;
    if (m>n)
    swap (n,m);
    for (i=0;i<=n+1;i++)
    {
        x[0][i]=-1;
        x[m+1][i]=-1;
        x[i][0]=-1;
        x[i][n+1]=-1;
        z[0][i]=-1;
        z[m+1][i]=-1;
        z[i][0]=-1;
        z[i][n+1]=-1;
    }
Lee();
    return 0;
}