Cod sursa(job #1852937)

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

using namespace std;

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

queue <pair <int,int> > q;

void refreshMat()
{
    for(int i=0; i<=M+1; i++)
    {
        v1[0][i]=-1;
        v1[N+1][i]=-1;
    }
    for(int i=0; i<=N+1; i++)
    {
        v1[i][0]=-1;
        v1[i][M+1]=-1;
    }

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            v2[i][j]=v1[i][j];

}

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

        printf("\n");
    }

    printf("\n");
    printf("\n");
    printf("\n");
    printf("\n");

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

        printf("\n");
    }

}

void lee(pair<int,int>rom1,pair<int,int>jul1,int v[105][105])
{
    q.push(rom1);
    v[rom1.first][rom1.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==jul1.first && yy==jul1.second)
                    return;
            }
        }
        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')
                v1[i][j+1]=-1;
            else if(x=='J')
                jul = {i,j+1};
            else if(x=='R')
                rom = {i,j+1};
        }
    }
    refreshMat();
    lee(rom,jul,v1);
    while(!q.empty())
        q.pop();
    lee(jul,rom,v2);

   afis();

    int nr=105*105;
    fin= {105,105};
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
        {
            if(v1[i][j]==v2[i][j] && v1[i][j]!=-1 && ( v1[i][j]<nr || (v1[i][j]<=nr && (i<fin.first || j<fin.second))))
            {
                nr=v1[i][j];
                fin= {i,j};
            }
        }


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


    return 0;
}