Cod sursa(job #219108)

Utilizator petroMilut Petronela petro Data 5 noiembrie 2008 15:31:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include<stdio.h>
#include<values.h>
#define M 101
FILE *f=fopen("rj.in","r");
FILE *g=fopen("rj.out","w");

char a[M][M];
int b[M][M],c[M][M],n,m,ij,jj,ir,jr,ci[10002],cj[10002];

void citire()
{int i,j;


 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
	{fscanf(f,"%c",&a[i][j]);

	  if(a[i][j]=='X') {b[i][j]=-1;
			    c[i][j]=-1;}

	  else if(a[i][j]==' ') {b[i][j]=MAXINT;
				 c[i][j]=MAXINT;}

	       else if(a[i][j]=='R') {ir=i;
				      jr=j;
				      b[i][j]=1;
				      c[i][j]=MAXINT;}

		    else if(a[i][j]=='J') {ij=i;
					   jj=j;
					   c[i][j]=1;
					   b[i][j]=MAXINT;}

			  else if(a[i][j]=='\n') if(i==n&&j==m) j++;
						 else j--;
	  }


  fclose(f);

 for(i=0;i<=n+1;i++)
  {b[i][0]=b[i][m+1]-1;
    c[i][0]=c[i][m+1]=-1;}

 for(j=0;j<=m+1;j++)
  b[0][j]=b[n+1][j]=c[0][j]=c[n+1][j]=-1;

  }

int drum()
{int p,u,i,j;

 p=u=1;
 ci[u]=ir;
 cj[u]=jr;

 b[ir][jr]=1;

 while(p<=u)
 {i=ci[p];
  j=cj[p];

  if(b[i+1][j]!=-1&&b[i+1][j]>b[i][j]+1) {u++;
					  ci[u]=i+1;
					  cj[u]=j;
					  b[i+1][j]=b[i][j]+1;}

  if(b[i+1][j-1]!=-1&&b[i+1][j-1]>b[i][j]+1) {u++;
					      ci[u]=i+1;
					      cj[u]=j-1;
					      b[i+1][j-1]=b[i][j]+1;}

  if(b[i][j-1]!=-1&&b[i][j-1]>b[i][j]+1) {u++;
					  ci[u]=i;
					  cj[u]=j-1;
					  b[i][j-1]=b[i][j]+1;}

  if(b[i-1][j-1]!=-1&&b[i-1][j-1]>b[i][j]+1) {u++;
					      ci[u]=i-1;
					      cj[u]=j-1;
					      b[i-1][j-1]=b[i][j]+1;}

  if(b[i-1][j]!=-1&&b[i-1][j]>b[i][j]+1) {u++;
					  ci[u]=i-1;
					  cj[u]=j;
					  b[i-1][j]=b[i][j]+1;}

  if(b[i-1][j+1]!=-1&&b[i-1][j+1]>b[i][j]+1) {u++;
					      ci[u]=i-1;
					      cj[u]=j+1;
					      b[i-1][j+1]=b[i][j]+1;}

  if(b[i][j+1]!=-1&&b[i][j+1]>b[i][j]+1) {u++;
					  ci[u]=i;
					  cj[u]=j+1;
					  b[i][j+1]=b[i][j]+1;}

  if(b[i+1][j+1]!=-1&&b[i+1][j+1]>b[i][j]+1) {u++;
					      ci[u]=i+1;
					      cj[u]=j+1;
					      b[i+1][j+1]=b[i][j]+1;}

  p++;}
return 0;
}

int drum1()
{int p,u,i,j;

 p=u=1;
 ci[u]=ij;
 cj[u]=jj;

 c[ij][jj]=1;

 while(p<=u)
 {i=ci[p];
  j=cj[p];

  if(c[i+1][j]!=-1&&c[i+1][j]>c[i][j]+1) {u++;
					  ci[u]=i+1;
					  cj[u]=j;
					  c[i+1][j]=c[i][j]+1;}

  if(c[i+1][j-1]!=-1&&c[i+1][j-1]>c[i][j]+1) {u++;
					      ci[u]=i+1;
					      cj[u]=j-1;
					      c[i+1][j-1]=c[i][j]+1;}

  if(c[i][j-1]!=-1&&c[i][j-1]>c[i][j]+1) {u++;
					  ci[u]=i;
					  cj[u]=j-1;
					  c[i][j-1]=c[i][j]+1;}

  if(c[i-1][j-1]!=-1&&c[i-1][j-1]>c[i][j]+1) {u++;
					      ci[u]=i-1;
					      cj[u]=j-1;
					      c[i-1][j-1]=c[i][j]+1;}

  if(c[i-1][j]!=-1&&c[i-1][j]>c[i][j]+1) {u++;
					  ci[u]=i-1;
					  cj[u]=j;
					  c[i-1][j]=c[i][j]+1;}

  if(c[i-1][j+1]!=-1&&c[i-1][j+1]>c[i][j]+1) {u++;
					      ci[u]=i-1;
					      cj[u]=j+1;
					      c[i-1][j+1]=c[i][j]+1;}

  if(c[i][j+1]!=-1&&c[i][j+1]>c[i][j]+1) {u++;
					  ci[u]=i;
					  cj[u]=j+1;
					  c[i][j+1]=c[i][j]+1;}

  if(c[i+1][j+1]!=-1&&c[i+1][j+1]>c[i][j]+1) {u++;
					      ci[u]=i+1;
					      cj[u]=j+1;
					      c[i+1][j+1]=c[i][j]+1;}

  p++;}

 return 0;

}

int main()
 {char d;

  int i,j,tmin=MAXINT;

  fscanf(f,"%d%d%c",&n,&m,&d);
  citire();

  drum();

  drum1();

 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
   if(b[i][j]==c[i][j]&&b[i][j]!=-1&&b[i][j]!=1) if(b[i][j]<tmin) {tmin=b[i][j];
					   ir=i;
					   jr=j;
					  }

 fprintf(g,"%d %d %d",tmin,ir,jr);


 fprintf(g,"\n");


  fclose(g);
return 0;
  }