Cod sursa(job #1853515)

Utilizator mariakKapros Maria mariak Data 21 ianuarie 2017 20:43:03
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<deque>
#include<cstdio>
#include<algorithm>
using namespace std;
int dx[8]={-1,0,1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int C1[10005],C2[10005],C3[10005];
int a[105][105],b[105][105],n,m,x1,i,j,k,in,sf,z,t,minn,xl,xc,xd,yl,yc,yd,x,y;
char s[105];
int main()
{
    int y1 = 0;
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1;i<=n;i++)
    {
        gets(s+1);
        for (j=1;j<=m;j++)
     {
         if (s[j]==' ') {a[i][j]=-2; b[i][j]=-2; }
         if (s[j]=='X') {a[i][j]=-1; b[i][j]=-1; }
         if (s[j]=='R') {x1=i; y1=j;}
         if (s[j]=='J') {z=i; t=j;}
     }
    }

     for (i=1;i<=n;i++) {a[i][0]=-1; b[i][0]=-1; }
     for (i=1;i<=m;i++) {a[0][i]=-1; b[0][i]=-1; }
     xl=x1; xc=y1; xd=0; a[xl][xc]=0;
     C1[in]=xl; C2[in]=xc; C3[in]=xd;
     while (in<=sf)
     {
         xl=C1[in]; xc=C2[in]; xd=C3[in]; in++;
         for (k=0;k<8;k++)
         {
             yl=xl+dx[k];
             yc=xc+dy[k];
             if (a[yl][yc]==-2)
             {
                 yd=xd+1;
                 a[yl][yc]=yd;
                 C1[++sf]=yl; C2[sf]=yc; C3[sf]=yd;
             }
         }
     }
    xl=z; xc=t; xd=0; b[xl][xc]=0; in=0; sf=0; minn=1000000000;
     C1[in]=xl; C2[in]=xc; C3[in]=xd;
     while (in<=sf)
     {
         xl=C1[in]; xc=C2[in]; xd=C3[in]; in++;
         for (k=0;k<8;k++)
         {
             yl=xl+dx[k];
             yc=xc+dy[k];
             if (b[yl][yc]==-2)
             {
                 yd=xd+1;
                 b[yl][yc]=yd;
                 if ((yd==a[yl][yc])&&(yd==minn))
                 {
                     if (yl<x) {x=yl; y=yc;}
                     if ((yl==x)&&(yc<y)) {x=yl; y=yc;}
                 }
                 if ((yd==a[yl][yc])&&(yd<minn)) {minn=yd; x=yl; y=yc; }
                 C1[++sf]=yl; C2[sf]=yc; C3[sf]=yd;
             }
         }
     }
     printf("%d %d %d",minn+1,x,y);
     return 0;
}