Cod sursa(job #1875532)

Utilizator RazvanGutaGuta Razvan Alexandru RazvanGuta Data 11 februarie 2017 11:15:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
short dx[]={-1,-1,0,1,1,1,0,-1};
short dy[]={0,1,1,1,0,-1,-1,-1};
struct elem{
  short l,c;
}q[10001],q1[1001];
int n,m,t1[101][101],xr,yr,xj,yj,i,j,b[101][101],c[101][101],t2[101][101],t,xf,yf,l;
char a[101],c1;
void lee1(short xs,short ys)
{
    int lv,cv,p,u;
    elem x;
    p=u=1;
    t1[xs][ys]=1;
    q[p].l=xs;
    q[p].c=ys;
    while(p<=u)
    {
        x=q[p];
        for(int k=0;k<8;k++)
        {
            lv=x.l+dx[k];
            cv=x.c+dy[k];
            if(lv>0&&lv<=n&&cv>0&&cv<=m)
            {
                if(b[lv][cv]==0)
                {
                    if(t1[lv][cv]<t1[x.l][x.c]+1)
                    {
                        u++;
                        q[u].l=lv;
                        q[u].c=cv;
                        t1[lv][cv]=t1[x.l][x.c]+1;
                    }
                    b[lv][cv]=1;
                }
            }
        }
    p++;

    }
}
void lee2(short xs,short ys)
{
    int lv,cv,p,u;
    elem x;
    p=u=1;
    t2[xs][ys]=1;
    q1[p].l=xs;
    q1[p].c=ys;
    while(p<=u)
    {
        x=q1[p];
        for(int k=0;k<8;k++)
        {
            lv=x.l+dx[k];
            cv=x.c+dy[k];
            if(lv>0&&lv<=n&&cv>0&&cv<=m)
            {
                if(c[lv][cv]==0)
                {
                    if(t2[lv][cv]<t2[x.l][x.c]+1)
                    {
                        u++;
                        q1[u].l=lv;
                        q1[u].c=cv;
                        t2[lv][cv]=t2[x.l][x.c]+1;
                    }
                    c[lv][cv]=1;
                }
            }
        }
    p++;

    }
}
int main ()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f.get();
       f.get(a,101);
       for(j=0;j<m;j++)
       {
           c1=a[j];
           if(c1=='X')
           {
               b[i][j+1]=1;
               c[i][j+1]=1;
           }
           if(c1==' ')
           {
               b[i][j+1]=0;
               c[i][j+1]=0;
           }
           if(c1=='R')
           {
               b[i][j+1]=0;
               c[i][j+1]=0;
               xr=i;
               yr=j+1;
           }
           if(c1=='J')
           {
               b[i][j+1]=0;
               c[i][j+1]=0;
               xj=i;
               yj=j+1;
           }
       }
    }
    lee1(xr,yr);
     t1[xr][yr]=1;
    lee2(xj,yj);
    t2[xj][yj]=1;
    t=999999999;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(t1[i][j]==t2[i][j])
            {
                if(t1[i][j]<t&&t1[i][j]>0)
                {
                    t=t1[i][j];
                    xf=i;
                    yf=j;
                }
            }
        }
    }
    g<<t<<" "<<xf<<" "<<yf;

    return 0;
}