Cod sursa(job #119495)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 1 ianuarie 2008 15:38:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<stdio.h>
#include<stdlib.h>
long int m,n,dx[10],dy[10],i,j,v1[102][102],v2[102][102],xr,yr,xj,yj,
l2,a2[10000],b2[10000],l1,a1[10000],b1[10000],xc,yc,xn,yn,t2[102][102],t1[102][102],
t,tmin,xsol,ysol,tmax;
char p[110];
int main()
{
    FILE *f,*g;f=fopen("rj.in","r");g=fopen("rj.out","w");
    fscanf(f,"%ld%ld",&m,&n);
    dx[0]=-1;dx[1]=-1;dx[2]=-1;dx[3]=0;dx[4]=0;dx[5]=1;dx[6]=1;dx[7]=1;
    dy[0]=-1;dy[1]=0;dy[2]=1;dy[3]=-1;dy[4]=1;dy[5]=-1;dy[6]=0;dy[7]=1;
    fgets(p,102,f);
    for(i=1;i<=m;i++){fgets(p,102,f);for(j=1;j<=n;j++){if(p[j-1]=='X'){v1[i][j]=1;v2[i][j]=1;}else if(p[j-1]=='R'){xr=i;yr=j;}else if(p[j-1]=='J'){xj=i;yj=j;}}}
    for(i=0;i<=m+1;i++){ v1[i][0]=1;v2[i][0]=1;v1[i][n+1]=1;v2[i][n+1]=1;}
    for(j=0;j<=n+1;j++){ v1[0][j]=1;v2[0][j]=1;v1[m+1][j]=1;v2[m+1][j]=1;}
    l1=1;a1[l1]=xr;b1[l1]=yr;
    while(!v1[xj][yj])
    {    t++;
	 l2=0;
	 for(i=1;i<=l1;i++){xc=a1[i];yc=b1[i];for(j=0;j<=7;j++){xn=xc+dx[j];yn=xc+dy[j];if(!v2[xn][yn]){l2++;a2[l2]=xn;b2[l2]=yn;}}v1[xc][yc]=1;t1[xc][yc]=t;}
	 t++;
	 l1=0;
	 for(i=1;i<=l2;i++){xc=a2[i];yc=b2[i];for(j=0;j<=7;j++){xn=xc+dx[j]; yn=xc+dy[j];if(!v1[xn][yn]){l1++;a1[l1]=xn;b1[l1]=yn;}}t2[xc][yc]=t;v2[xc][yc]=1;}
    }
    tmin=(t1[xj][yj]+1)/2;
    fprintf(g,"%ld ",tmin);
    tmax=t1[xj][yj];
    xsol=xj;ysol=yj;
    while(tmax>tmin)
    { tmax--;
      for(j=0;j<=7;j++)
      { if(t2[xsol+dx[j]][ysol+dy[j]]==tmax)
	 {xsol=xsol+dx[j];ysol=ysol+dy[j];break;}
	if(t1[xsol+dx[j]][ysol+dy[j]]==tmax)
	 {xsol=xsol+dx[j];ysol=ysol+dy[j];break;}
      }
    }
    fprintf(g,"%ld %ld\n",xsol,ysol);
    fcloseall();
    return 0;
}