Cod sursa(job #177800)

Utilizator katakunaCazacu Alexandru katakuna Data 13 aprilie 2008 16:51:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
#define INF 11000

int min,n,i,j,p,u,x1,x2,x,y,y1,m,y2,a[110][110],b[110][110],co[2][11000],d[2][8]={{1,0,-1,0,1,1,-1,-1},{0,1,0,-1,1,-1,1,-1}};
char c[110][110],cc;

int main(){



FILE *f=fopen("rj.in","r");

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


for(i=1;i<=n;i++)
c[i][0]='0';


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

      if(c[i][j]=='R'){
      x1=i;
      y1=j;
      }


      if(c[i][j]=='J'){
      x2=i;
      y2=j;
      }

    }

  fscanf(f,"%c",&cc);
  }


fclose(f);



for(i=1;i<=n;i++){
  for(j=1;j<=m;j++){
  a[i][j]=b[i][j]=INF;
  }
}



p=1;
u=1;

co[0][p]=x1;
co[1][p]=y1;
a[x1][y1]=1;

  while(p<=u){

      for(i=0;i<=7;i++){
      x=co[0][p]+d[0][i];
      y=co[1][p]+d[1][i];


	 if(c[x][y]==' '&&a[x][y]>a[co[0][p]][co[1][p]]+1&&x>=1&&x<=n&&y>=1&&y<=m){
	 u++;
	 co[0][u]=x;
	 co[1][u]=y;

	 a[x][y]=a[co[0][p]][co[1][p]]+1;

	 }


      }


  p++;
  }


p=1;
u=1;

co[0][p]=x2;
co[1][p]=y2;
b[x2][y2]=1;

  while(p<=u){

      for(i=0;i<=7;i++){
      x=co[0][p]+d[0][i];
      y=co[1][p]+d[1][i];


	 if(c[x][y]==' '&&b[x][y]>b[co[0][p]][co[1][p]]+1&&x>=1&&x<=n&&y>=1&&y<=m){
	 u++;
	 co[0][u]=x;
	 co[1][u]=y;

	 b[x][y]=b[co[0][p]][co[1][p]]+1;

	 }


      }


  p++;
  }

min=12100;


  for(i=1;i<=n;i++){
    for(j=1;j<=m;j++){

      if(a[i][j]&&a[i][j]==b[i][j]&&a[i][j]<min){
      min=a[i][j];
      x=i;
      y=j;
      }


    }
  }


FILE *g=fopen("rj.out","w");
fprintf(g,"%d %d %d",min,x,y);
fclose(g);

return 0;
}