Cod sursa(job #2466036)

Utilizator traiandobrinDobrin Traian traiandobrin Data 1 octombrie 2019 11:55:56
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <fstream>
#include <vector>
#include <cstring>
#define pii pair <int,int>
#define x first
#define y second
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
int r[105][105],j[105][105];
char a[105][105];
int xj,n,m,yj,xr,yr,limv,ind=1,ans=105*105,xx,yy;
pii vecini[105*105*10];
pii nextt[105*105*10];
void updater(int p,int d)
{
    int i,xi=vecini[p].x,xy=vecini[p].y;
    if(r[xy][xi]==0)
        r[xy][xi]=d;
    else
        return ;
    int dir1[]={0,0,0,1,-1,1,-1,1,-1};
    int dir2[]={0,1,-1,0,0,1,-1,-1,1};
    if(xi==xr && xy==yr)
        r[xy][xr]=-1;
    for(i=1;i<=8;++i)
    {
        if(xy+dir1[i]>0 && xi+dir2[i]<=m && xi+dir2[i]>0 && xy+dir1[i]<=n && (a[xy+dir1[i]][xi+dir2[i]]==32 || a[xy+dir1[i]][xi+dir2[i]]=='J' || a[xy+dir1[i]][xi+dir2[i]]=='R') && r[xy+dir1[i]][xi+dir2[i]]==0)
        {   int a,b;
            nextt[ind].y=a=xy+dir1[i];
            nextt[ind].x=b=xi+dir2[i];
            ++ind;
        }
    }

}
void updatej(int p,int d)
{
        int i,xi=vecini[p].x,xy=vecini[p].y;
    if(j[xy][xi]==0)
        j[xy][xi]=d;
    else
        return ;
    int dir1[]={0,0,0,1,-1,1,-1,1,-1};
    int dir2[]={0,1,-1,0,0,1,-1,-1,1};
    if(j[xy][xi]==r[xy][xi])
    {
        if(ans>d || (ans==d && yy>xy))
            ans=d,xx=xi,yy=xy;
    }
    if(xi==xj && xy==yj)
        j[yj][xj]=-1;
    for(i=1;i<=8;++i)
    {
        if(xy+dir1[i]>0 && xi+dir2[i]<=m && xi+dir2[i]>0 && xy+dir1[i]<=n && (a[xy+dir1[i]][xi+dir2[i]]==32 || a[xy+dir1[i]][xi+dir2[i]]=='J' || a[xy+dir1[i]][xi+dir2[i]]=='R') && j[xy+dir1[i]][xi+dir2[i]]==0 )
        {   int a,b;
            nextt[ind].y=a=xy+dir1[i];
            nextt[ind].x=b=xi+dir2[i];
            ++ind;
        }
    }

}
int main()
{
    int i=1,jj;
    char c;
    cin>>n>>m;
    cin.get(c);
    while(i<=n)
    {   jj=1;
        while(cin.get(a[i][jj]))
     {  if(a[i][jj]=='\n') break;
         ++jj;
         c=a[i][jj-1];
     if(a[i][jj-1]=='J')
        xj=jj-1,yj=i;
     if(a[i][jj-1]=='R')
        xr=jj-1,yr=i;
    }
        ++i;
    }
    vecini[1].x=xr;
    vecini[1].y=yr;
    int vecmax=1;
    int d=0;
    limv=1;
    //lee romeo
    do
    {   int exi=ind;
        for(int p=limv;p<exi || p<=1;++p)
        {
            updater(p,d);
        }
        vecmax=ind;
        for(int p=exi;p<ind;++p)
            vecini[p].x=nextt[p].x,vecini[p].y=nextt[p].y;
            limv=exi;
            if(exi==ind)
                limv=0;
    ++d;
    }while(limv);
    //lee julieta
    limv=1;
    d=0;
    ind=1;
    vecini[1].x=xj;
    vecini[1].y=yj;
    do
    {   int exi=ind;
        for(int p=limv;p<exi || p<=1;++p)
        {
            updatej(p,d);
        }
        vecmax=ind;
        for(int p=exi;p<ind;++p)
            vecini[p].x=nextt[p].x,vecini[p].y=nextt[p].y;
            limv=exi;
        if(exi==ind)
            limv=0;
        ++d;
    }while(limv);
    /*for(i=1;i<=n;++i)
    {
        for(jj=1;jj<=m;++jj)
            cout<<r[i][jj]<<" ";
        cout<<endl;
    }*/
    cout<<ans+1<<" "<<yy<<" "<<xx;//<<" "<<a[12][4];
    return 0;
}