Cod sursa(job #865840)

Utilizator raulmuresanRaul Muresan raulmuresan Data 27 ianuarie 2013 09:30:50
Problema Rj Scor 100
Compilator cpp Status done
Runda 23_reloaded_1 Marime 5.29 kb
#include <cstdio>

using namespace std;
struct romeo
{
    int x,y;
} c[100000];

struct julieta
{
    int x,y;
} d[100000];
char text[110];
short int a[102][102],r[102][102];
int n,m,i,j,x1,x2,y1,y2,dr,st,rx,ry,jx,jy,maxi,t;

void romeo( int k)
{
    int lin,col;
    lin=c[k].x;
    col=c[k].y;
   //printf("%d,%d - %hd\n",lin,col,r[lin][col]);
  if(r[lin][col]!=-1){
    //sus
    if (lin-1>=1 &&  r[lin-1][col]==0)
    {
        r[lin-1][col]=r[lin][col]+1;
        dr++;
        c[dr].x=lin-1;
        c[dr].y=col;
    }
    //dreapta
    if(col+1 <=m &&   r[lin][col+1]==0)
    {
        r[lin][col+1]=r[lin][col]+1;
        dr++;
        c[dr].x=lin;
        c[dr].y=col+1;
    }
    //jos
    if (lin+1<=n &&   r[lin+1][col]==0)
    {
        r[lin+1][col]=r[lin][col]+1;
        dr++;
        c[dr].x=lin+1;
        c[dr].y=col;
    }

    //stanga
    if(col-1 >=1 &&  r[lin][col-1]==0)
    {
        r[lin][col-1]=r[lin][col]+1;
        dr++;
        c[dr].x=lin;
        c[dr].y=col-1;
    }
    //SUD-EST
    if(col+1 <=m && lin+1<=n &&  r[lin+1][col+1]==0)
    {
        r[lin+1][col+1]=r[lin][col]+1;
        dr++;
        c[dr].x=lin+1;
        c[dr].y=col+1;
    }
    //SUD-VEST
    if(col-1 >=1 && lin+1<=n &&  r[lin+1][col-1]==0)
    {
        r[lin+1][col-1]=r[lin][col]+1;
        dr++;
        c[dr].x=lin+1;
        c[dr].y=col-1;
    }

    //NORD-EST
    if(col+1 <=m && lin-1>=1 &&  r[lin-1][col+1]==0)
    {
        r[lin-1][col+1]=r[lin][col]+1;
        dr++;
        c[dr].x=lin-1;
        c[dr].y=col+1;
    }
    //NORD-VEST
    if(col-1 >=1 && lin-1>=1 &&  r[lin-1][col-1]==0)
    {
        r[lin-1][col-1]=r[lin][col]+1;
        dr++;
        c[dr].x=lin-1;
        c[dr].y=col-1;
    }


  }
}



void julieta( int k)
{
    int lin,col;
    lin=d[k].x;
    col=d[k].y;
   //printf("%d,%d - %hd\n",lin,col,r[lin][col]);
  if(a[lin][col]!=-1){
    //sus
    if (lin-1>=1 &&  a[lin-1][col]==0)
    {
        a[lin-1][col]=a[lin][col]+1;
        dr++;
        d[dr].x=lin-1;
        d[dr].y=col;
    }
    //dreapta
    if(col+1 <=m &&   a[lin][col+1]==0)
    {
        a[lin][col+1]=a[lin][col]+1;
        dr++;
        d[dr].x=lin;
        d[dr].y=col+1;
    }
    //jos
    if (lin+1<=n &&   a[lin+1][col]==0)
    {
        a[lin+1][col]=a[lin][col]+1;
        dr++;
        d[dr].x=lin+1;
        d[dr].y=col;
    }

    //stanga
    if(col-1 >=1 &&  a[lin][col-1]==0)
    {
        a[lin][col-1]=a[lin][col]+1;
        dr++;
        d[dr].x=lin;
        d[dr].y=col-1;
    }
    //SUD-EST
    if(col+1 <=m && lin+1<=n &&  a[lin+1][col+1]==0)
    {
        a[lin+1][col+1]=a[lin][col]+1;
        dr++;
        d[dr].x=lin+1;
        d[dr].y=col+1;
    }
    //SUD-VEST
    if(col-1 >=1 && lin+1<=n &&  a[lin+1][col-1]==0)
    {
        a[lin+1][col-1]=a[lin][col]+1;
        dr++;
        d[dr].x=lin+1;
        d[dr].y=col-1;
    }

    //NORD-EST
    if(col+1 <=m && lin-1>=1 &&  a[lin-1][col+1]==0)
    {
        a[lin-1][col+1]=a[lin][col]+1;
        dr++;
        d[dr].x=lin-1;
        d[dr].y=col+1;
    }
    //NORD-VEST
    if(col-1 >=1 && lin-1>=1 &&  a[lin-1][col-1]==0)
    {
        a[lin-1][col-1]=a[lin][col]+1;
        dr++;
        d[dr].x=lin-1;
        d[dr].y=col-1;
    }


  }
}
int main()
{
    freopen ("rj.in","r",stdin);
    freopen ("rj.out","w",stdout);
    scanf("%d\n",&n);
    scanf("%d\n",&m);
    for(i=1;i<=n;i++)
        {
            gets(text);
            for(j=0;j<=m-1;j++){
                if(text[j]=='X'){
                a[i][j+1]=-1;
                r[i][j+1]=-1;
                }
                else{
                if(text[j]=='R'){
                rx=i;ry=j+1;
                }
                if(text[j]=='J'){
                jx=i;jy=j+1;
                }
                }
            }

        }
    c[1].x=rx;
    c[1].y=ry;
    d[1].x=jx;
    d[1].y=jy;
    st=dr=1; // capetele de la coada
    r[rx][ry]=1;
    a[jx][jy]=1;
    //printf("%d ",n);
    //printf("%d ",m);
     /*for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                printf("%hd ",a[i][j]);
        }
        printf("\n");
     }*/
     st=dr=1;

    for(t=st;t<=dr;t++){
            romeo(t);
             /*for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                printf("%hd ",a[i][j]);
        }
        printf("\n");
        }*/

    }
    st=dr=1;
    for(i=st;i<=dr;i++){
            julieta(i);
    }
    //printf("%d ",n);
    //printf("%d ",m);
    maxi=100000;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(a[i][j]==r[i][j] && r[i][j]!=-1 && r[i][j]<maxi && r[i][j]!=-0)
                {
                    maxi=r[i][j];
                    x1=i;
                    x2=j;
                }
        }
        //printf("\n");
        }

        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
              //  printf("%hd ",r[i][j]);
        }
     //   printf("\n");
        }
   // printf("\n\n\n\n\n");
 for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                //printf("%hd ",a[i][j]);
        }
       // printf("\n");
        }


        printf("%d %d %d",maxi,x1,x2);
       // printf("%d %d\n",jx,jy);

}