Cod sursa(job #155017)

Utilizator otilia_sOtilia Stretcu otilia_s Data 11 martie 2008 17:43:51
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <stdio.h>
FILE *fin=fopen("rj.in","r");
FILE *fout=fopen("rj.out","w");
typedef struct {int x,y;} pozitie;
int a[102][102],i,h,m,n,inc,sf,l,c,dr[102][102] ;
pozitie r,j;
char ch;

void drum_r()
{ int ii,jj,tmin,xi,yi;
  pozitie C[10002];
 for (ii=1;ii<=n;ii++) for (jj=1;jj<=m;jj++) dr[ii][jj]=a[ii][jj];
 inc=sf=0; C[0]=r; dr[r.x][r.y]=0;
 while (inc<=sf)
  {
   l=C[inc].x; c=C[inc].y;
   if (l>1&&dr[l-1][c]>-1)
      if (dr[l-1][c]>dr[l][c]+1) {
				  dr[l-1][c]=dr[l][c]+1;
				  C[++sf].x=l-1; C[sf].y=c;
				 }
   if (l<n&&dr[l+1][c]>-1)
      if (dr[l+1][c]>dr[l][c]+1) { dr[l+1][c]=dr[l][c]+1;
				   C[++sf].x=l+1; C[sf].y=c;
			       }
   if (c>1&&dr[l][c-1]>-1)
      if (dr[l][c-1]>dr[l][c]+1) { dr[l][c-1]=dr[l][c]+1;
				  C[++sf].x=l; C[sf].y=c-1;
			       }
   if (c<m&&dr[l][c+1]>-1)
      if (dr[l][c+1]>dr[l][c]+1) { dr[l][c+1]=dr[l][c]+1;
				  C[++sf].x=l; C[sf].y=c+1;
				}
   if (l>1&&c>1&&dr[l-1][c-1]>-1)
      if (dr[l-1][c-1]>dr[l][c]+1){ dr[l-1][c-1]=dr[l][c]+1;
				    C[++sf].x=l-1; C[sf].y=c-1;
				  }
   if (l>1&&c<m&&dr[l-1][c+1]>-1)
      if (dr[l-1][c+1]>dr[l][c]+1){ dr[l-1][c+1]=dr[l][c]+1;
				    C[++sf].x=l-1; C[sf].y=c+1;
				  }
   if (l<n&&c>1&&dr[l+1][c-1]>-1)
      if (dr[l+1][c-1]>dr[l][c]+1){ dr[l+1][c-1]=dr[l][c]+1;
				    C[++sf].x=l+1; C[sf].y=c-1;
				  }
   if (l<n&&c<m&&dr[l+1][c+1]>-1)
      if (dr[l+1][c+1]>dr[l][c]+1){ dr[l+1][c+1]=dr[l][c]+1;
				    C[++sf].x=l+1; C[sf].y=c+1;
				  }
   inc++;
  }
// printf("%d\n",sf);
}

void drum_j()
{pozitie C[10002];
 int ii,jj, dj[102][102],tmin,xi,yi;
 for (ii=1;ii<=n;ii++) for (jj=1;jj<=m;jj++) dj[ii][jj]=a[ii][jj];
 inc=sf=0; C[0]=j; dj[j.x][j.y]=0;
 while (inc<=sf)
  {
   l=C[inc].x; c=C[inc].y;
   if (l>1&&dj[l-1][c]>-1)
      if (dj[l-1][c]>dj[l][c]+1) {
				  dj[l-1][c]=dj[l][c]+1;
				  C[++sf].x=l-1; C[sf].y=c;
				 }
   if (l<n&&dj[l+1][c]>-1)
      if (dj[l+1][c]>dj[l][c]+1) { dj[l+1][c]=dj[l][c]+1;
				   C[++sf].x=l+1; C[sf].y=c;
			       }
   if (c>1&&dr[l][c-1]>-1)
      if (dj[l][c-1]>dj[l][c]+1) { dj[l][c-1]=dj[l][c]+1;
				  C[++sf].x=l; C[sf].y=c-1;
			       }
   if (c<m&&dr[l][c+1]>-1)
      if (dj[l][c+1]>dj[l][c]+1) { dj[l][c+1]=dj[l][c]+1;
				  C[++sf].x=l; C[sf].y=c+1;
				}
   if (l>1&&c>1&&dj[l-1][c-1]>-1)
      if (dj[l-1][c-1]>dj[l][c]+1){ dj[l-1][c-1]=dj[l][c]+1;
				    C[++sf].x=l-1; C[sf].y=c-1;
				  }
   if (l>1&&c<m&&dj[l-1][c+1]>-1)
      if (dj[l-1][c+1]>dj[l][c]+1){ dj[l-1][c+1]=dj[l][c]+1;
				    C[++sf].x=l-1; C[sf].y=c+1;
				  }
   if (l<n&&c>1&&dj[l+1][c-1]>-1)
      if (dj[l+1][c-1]>dj[l][c]+1){ dj[l+1][c-1]=dj[l][c]+1;
				    C[++sf].x=l+1; C[sf].y=c-1;
				  }
   if (l<n&&c<m&&dj[l+1][c+1]>-1)
      if (dj[l+1][c+1]>dj[l][c]+1){ dj[l+1][c+1]=dj[l][c]+1;
				    C[++sf].x=l+1; C[sf].y=c+1;
				  }
   inc++;
  }
 tmin=30000; xi=yi=200;
 for (ii=1;ii<=n;ii++)
  for (jj=1;jj<=m;jj++)
   if (dr[ii][jj]==dj[ii][jj])
      if (dr[ii][jj]>-1&&tmin>dr[ii][jj]) {tmin=dr[ii][jj]; xi=ii; yi=jj;}
 fprintf(fout,"%d %d %d\n",tmin+1,xi,yi);
}

int main()
{
 fscanf(fin,"%d%d",&n,&m);
 fscanf(fin,"%c",&ch); // citim "\n"
 for (i=1;i<=n;i++)
  {
    for (h=1;h<=m;h++)
     {
      fscanf(fin,"%c",&ch);
      if (ch==' ') a[i][h]=30000; else
      if (ch=='X') a[i][h]=-1; else
      if (ch=='R') {r.x=i; r.y=h; a[i][h]=30000;} else
      if (ch=='J') {j.x=i; j.y=h; a[i][h]=30000;}
     }
    fscanf(fin,"%c",&ch); //citim '\n'
  }
 drum_r();
 drum_j();
 fclose(fin); fclose(fout);
return 0;
}