Cod sursa(job #80641)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 29 august 2007 07:34:11
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<stdio.h>
#include<stdlib.h>
struct nod{
long int x;
long int y;
nod *next;
};
nod *prim,*ultim,*ppp;
char p[105],*pp;
long int m,n,tmin,i,j,R[102][102],J[102][102],xr,yr,xj,yj,xp,yp,xs,ys,mark,
dx[10],dy[10],xsol,ysol;
void pune(long int xx,long int yy);
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;
    tmin=m*n+10;
    for(i=0;i<=m+1;i++){R[i][0]=tmin;R[i][n+1]=tmin;J[i][0]=tmin;J[i][n+1]=tmin;}
    for(j=0;j<=n+1;j++){R[0][j]=tmin;R[m+1][j]=tmin;J[0][j]=tmin;J[m+1][j]=tmin;}
    pp=&p[0];fgets(pp,102,f);
    for(i=1;i<=m;i++){fgets(pp,102,f);for(j=1;j<=n;j++){ if(p[j-1]=='X'){R[i][j]=tmin;J[i][j]=tmin;}else if(p[j-1]=='R'){xr=i;yr=j;}else if(p[j-1]=='J'){xj=i;yj=j;}}}
    prim=new nod;prim=0;ultim=new nod;ultim=0;
    R[xr][yr]=1;pune(xr,yr);
    while(prim)
    {   xp=prim->x;yp=prim->y;mark=R[xp][yp]+1;
	for(i=0;i<=7;i++)
	 { xs=xp+dx[i];ys=prim->y+dy[i];
	   if(!R[xs][ys]){R[xs][ys]=mark;pune(xs,ys);}
	 }
	ppp=new nod;ppp=prim;prim=prim->next;free(ppp);
    }
    J[xj][yj]=1;pune(xj,yj);
    while(prim)
    {   xp=prim->x;yp=prim->y;mark=J[xp][yp]+1;
	for(i=0;i<=7;i++)
	 { xs=xp+dx[i];ys=prim->y+dy[i];
	   if(!J[xs][ys]){J[xs][ys]=mark;pune(xs,ys);}
	 }
	 ppp=new nod;ppp=prim;prim=prim->next;free(ppp);
    }
    for(i=1;i<=m;i++)
     for(j=1;j<=n;j++)
      if(R[i][j])
       if(R[i][j]==J[i][j])
	if(R[i][j]<tmin)
	 {xsol=i;ysol=j;tmin=R[i][j];}
     fprintf(g,"%ld %ld %ld\n",tmin,xsol,ysol);
     fcloseall();
     return 0;
}
void pune(long int xx,long int yy)
{
	nod *paux;
	paux=new nod;
	paux->x=xx;paux->y=yy;paux->next=0;
	if(!prim)
	{prim=paux;ultim=paux;return;}
	ultim->next=paux;ultim=paux;
}