Cod sursa(job #1852696)

Utilizator andysoloAndrei Solo andysolo Data 21 ianuarie 2017 09:41:27
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

pair <int ,int> rom,jul,fin;
int N,M,v[101][101],nr;
int dx[9]= {0,0,0,1,1,1,-1,-1,-1};
int dy[9]= {0,1,-1,+1,-1,0,1,-1,0};

queue <pair <int,int> > q;

void afis()
{
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
            printf("%d ",v[i][j]);

        printf("\n");
    }
}

pair<int,int> drum(pair<int,int> p)
{
    int x=p.first;
    int y=p.second;
    for(int i=1; i<=8; i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(v[xx][yy]==nr)
            return {xx,yy};
        else if(v[xx][yy]==v[x][y]-1)
            return drum({xx,yy});
    }
}

int lee(pair<int,int>rom,pair<int,int>jul)
{
    q.push(rom);
    v[rom.first][rom.second]=1;
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;

        for(int i=1; i<=8; i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];

            if(v[xx][yy]==0)
            {
                q.push({xx,yy});
                v[xx][yy]=v[x][y]+1;
                if(xx==jul.first && yy==jul.second && v[xx][yy]%2==1)
                    return v[xx][yy]/2+1;
            }
        }
        q.pop();
    }
}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    scanf("%d %d",&N,&M);
    cin.get();
    for(int i=1; i<=N; i++)
    {
        char s[101];
        cin.get(s,M+1);
        cin.get();
   //     cout<<s<<endl;
        for(int j=0; j<=M-1; j++)
        {
            char x=s[j];
            if(x=='X')
                v[i][j+1]=-1;
            else if(x=='J')
                jul = {i,j+1};
            else if(x=='R')
                rom = {i,j+1};
        }
    }
    for(int i=0; i<=M+1; i++)
    {
        v[0][i]=-1;
        v[N+1][i]=-1;
    }
    for(int i=0; i<=N+1; i++)
    {
        v[i][0]=-1;
        v[i][M+1]=-1;
    }
    nr=0;
    nr=lee(rom,jul);

    fin=drum(jul);

 //   afis();

    printf("%d %d %d",nr,fin.first,fin.second);


    return 0;
}