Cod sursa(job #1798666)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 5 noiembrie 2016 12:43:12
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int J[120][120],R[120][120];
char x;
int n,m,r1,r2,j1,j2,mini=100000000,imin,jmin;

queue<pair<int, int> >Q;
int di[8]={-1,1,0,0,-1,1,-1,1};
int dj[8]={0,0,1,-1,-1,1,1,-1};

void citire()
{
    scanf("%d %d\n",&n, &m);
    for(int i=1;i<=n;i++)
    {
          for(int j=1;j<=m;j++)
        {
            scanf("%c",&x);
            if(x=='X')
                {
                   J[i][j]=2;
                   R[i][j]=2;
                }
            else
                if(x=='R')
                    {
                       r1=i;
                       r2=j;
                    }
                else
                    if(x=='J')
                        {
                            j1=i;
                            j2=j;
                        }
        }
        scanf("%c",&x);
    }
}

void bordare()
{
    for(int i=0;i<=n+1;i++)
    {
        J[i][0]=-1;
        R[i][0]=-1;
        J[i][m+1]=-1;
        R[i][m+1]=-1;
    }
    for(int j=0;j<=m+1;j++)
    {
        J[0][j]=-1;
        R[0][j]=-1;
        J[n+1][j]=-1;
        R[n+1][j]=-1;
    }
}

void lee(int x1, int x2, int a[120][120])
{
    Q.push(make_pair(x1,x2));
    a[x1][x2]=1;
    while(!Q.empty())
    {
        int ic=Q.front().first;
        int jc=Q.front().second;
        Q.pop();
        for(int i=0;i<8;i++)
        {
            int iv=ic+di[i];
            int jv=jc+dj[i];
            if(!a[iv][jv])
            {
                Q.push(make_pair(iv,jv));
                a[iv][jv]=1+a[ic][jc];
                if(iv==r1 && jv==r2)
                    return;
            }
        }
    }
}

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

    citire();
    bordare();
    lee(r1, r2, R);
    lee(j1, j2, J);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(R[i][j]>0 && R[i][j]==J[i][j] && R[i][j]<mini)
            {
                mini=R[i][j];
                imin=i;
                jmin=j;
            }
        }
    cout<<mini<<" "<<imin<<" "<<jmin;
    return 0;
}