Cod sursa(job #1992390)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 20 iunie 2017 13:13:16
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fi("rj.in");
ofstream fo("rj.out");
int A[102][102],R[102][102],J[102][102],i,j,n,m,xr,yr,xj,yj,xl,yl,tmin=10001;
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
char c;
pair <int,int> p,q1,q2;
deque <pair <int,int> > D;
void romeo(int x,int y)
{
    int k;
    p.first=x;
    p.second=y;
    D.push_back(p);
    while(!D.empty())
    {
        q1=D.front();
        D.pop_front();
        for(k=0;k<=7;k++)
        {
            if(A[q1.first+dl[k]][q1.second+dc[k]]==0 && R[q1.first+dl[k]][q1.second+dc[k]]==0)
            {
                R[q1.first+dl[k]][q1.second+dc[k]]=R[q1.first][q1.second]+1;
                q2.first=q1.first+dl[k];
                q2.second=q1.second+dc[k];
                D.push_back(q2);
            }
        }
    }
}
void julieta(int x,int y)
{
    int k;
    p.first=x;
    p.second=y;
    D.push_back(p);
    while(!D.empty())
    {
        q1=D.front();
        D.pop_front();
        for(k=0;k<=7;k++)
        {
            if(A[q1.first+dl[k]][q1.second+dc[k]]==0 && J[q1.first+dl[k]][q1.second+dc[k]]==0)
            {
                J[q1.first+dl[k]][q1.second+dc[k]]=J[q1.first][q1.second]+1;
                q2.first=q1.first+dl[k];
                q2.second=q1.second+dc[k];
                D.push_back(q2);
            }
        }
    }
}
int main()
{
    fi>>n>>m;
    for(i=1;i<=n;i++)
    {
        A[i][0]=-1;
        A[i][m+1]=-1;
    }
    for(j=1;j<=m;j++)
    {
        A[0][j]=-1;
        A[n+1][j]=-1;
    }
    for(i=1;i<=n;i++)
    {
        c=fi.get();
        for(j=1;j<=m;j++)
        {
            c=fi.get();
            if(c=='X')
                A[i][j]=-1;
            if(c==' ')
                A[i][j]=0;
            if(c=='R')
            {
                A[i][j]=0;
                xr=i;
                yr=j;
            }
            if(c=='J')
            {
                A[i][j]=0;
                xj=i;
                yj=j;
            }
        }
    }
    R[xr][yr]=1;
    romeo(xr,yr);
    J[xj][yj]=1;
    julieta(xj,yj);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            if(R[i][j]==J[i][j] && R[i][j]<tmin && R[i][j]!=0)
            {
                xl=i;
                yl=j;
                tmin=R[i][j];
            }
    }
    fo<<tmin<<" "<<xl<<" "<<yl;
    fi.close();
    fo.close();
    return 0;
}