Cod sursa(job #99445)

Utilizator CosminStirbuStirbu Cosmin CosminStirbu Data 11 noiembrie 2007 11:38:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include<stdio.h>
int a1[100][100],a2[100][100],i,j,n,m,u,p,u1,p1,ok,tmin,x,y;
int main()
{ typedef struct { int c,l;} COADA;
  COADA cd1[10000],cd2[10000],x1,x2;
  char ch[100],c2;
  FILE*f=fopen("rj.in","r");
  FILE*g=fopen("rj.out","w");
  fscanf(f,"%d%d%c",&n,&m,&c2);
  for (i=1;i<=n;i++)
   {fgets (ch,100,f);
    for(j=0;j<m;j++)
       switch(ch[j])
	 { case 'X': a1[i][j+1]=a2[i][j+1]=-1;break;
	   case 'R': a1[i][j+1]=a2[i][j+1]=1;x1.l=i;x1.c=j+1;break;
	   case 'J': a1[i][j+1]=a2[i][j+1]=1;x2.l=i;x2.c=j+1;break;
	   default: break; }}
  for (i=1;i<=n;i++)
    {a1[i][0]=a1[i][m+1]=a1[0][0]=a1[n+1][0]=-1;
     a2[i][0]=a2[i][m+1]=a2[0][0]=a2[n+1][0]=-1;}
  for (i=1;i<=m+1;i++)
   { a1[0][i]=a1[n+1][i]=-1;
     a2[0][i]=a2[n+1][i]=-1;  }
  u1=p1=u=p=1;cd1[p]=x1;cd2[p1]=x2;
  ok=0;
  while (!ok)
   { x1=cd1[p++];x2=cd2[p1++];
     if (a1[x1.l-1][x1.c-1]==0)
	{a1[x1.l-1][x1.c-1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l-1;
	 cd1[u].c=x1.c-1;}
     if (a1[x1.l+1][x1.c+1]==0)
	{a1[x1.l+1][x1.c+1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l+1;
	 cd1[u].c=x1.c+1;}
     if (a1[x1.l-1][x1.c]==0)
	{a1[x1.l-1][x1.c]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l-1;
	 cd1[u].c=x1.c;}
     if (a1[x1.l+1][x1.c]==0)
	{a1[x1.l+1][x1.c]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l+1;
	 cd1[u].c=x1.c;}
     if (a1[x1.l][x1.c-1]==0)
	{a1[x1.l][x1.c-1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l;
	 cd1[u].c=x1.c-1;}
     if (a1[x1.l][x1.c+1]==0)
	{a1[x1.l][x1.c+1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l;
	 cd1[u].c=x1.c+1;}
     if (a1[x1.l-1][x1.c+1]==0)
	{a1[x1.l-1][x1.c+1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l-1;
	 cd1[u].c=x1.c+1;}
     if (a1[x1.l+1][x1.c-1]==0)
	{a1[x1.l+1][x1.c-1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l+1;
	 cd1[u].c=x1.c-1;}
     if (a1[x1.l+1][x1.c+1]==0)
	{a1[x1.l+1][x1.c+1]=a1[x1.l][x1.c]+1;
	 cd1[++u].l=x1.l+1;
	 cd1[u].c=x1.c+1;}




     if (a2[x2.l-1][x2.c-1]==0)
	{a2[x2.l-1][x2.c-1]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l-1;
	 cd2[u1].c=x2.c-1;}
     if (a2[x2.l+1][x2.c+1]==0)
	{a2[x2.l+1][x2.c+1]=a1[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l+1;
	 cd2[u1].c=x2.c+1;}
     if (a2[x2.l-1][x2.c]==0)
	{a2[x2.l-1][x2.c]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l-1;
	 cd2[u1].c=x2.c;}
     if (a2[x2.l+1][x2.c]==0)
	{a2[x1.l+1][x2.c]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l+1;
	 cd2[u1].c=x2.c;}
     if (a2[x2.l][x2.c-1]==0)
	{a2[x2.l][x2.c-1]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l;
	 cd2[u1].c=x2.c-1;}
     if (a2[x2.l][x2.c+1]==0)
	{a2[x2.l][x2.c+1]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l;
	 cd2[u1].c=x2.c+1;}
     if (a2[x2.l-1][x2.c+1]==0)
	{a2[x2.l-1][x2.c+1]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l-1;
	 cd2[u1].c=x2.c+1;}
     if (a2[x2.l+1][x2.c-1]==0)
	{a2[x2.l+1][x2.c-1]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l+1;
	 cd2[u1].c=x2.c-1;}
     if (a2[x2.l+1][x2.c+1]==0)
	{a2[x2.l+1][x2.c+1]=a2[x2.l][x2.c]+1;
	 cd2[++u1].l=x2.l+1;
	 cd2[u1].c=x2.c+1;}
     tmin=11000;
     for (i=p;i<=u;i++)
	if (a1[cd1[i].l][cd1[i].c]==a2[cd1[i].l][cd1[i].c])
	    if (a1[cd1[i].l][cd1[i].c]<tmin)
	       { tmin=a1[cd1[i].l][cd1[i].c];
		 x=cd1[i].l;
		 y=cd1[i].c;
		 ok=1;}
   }
 fprintf(g,"%d %d %d",tmin,x,y);
 fclose(f);fclose(g);
 return 0;}