Cod sursa(job #155512)

Utilizator codrinCodrin LACHE codrin Data 11 martie 2008 23:13:40
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<fstream.h>

int rom[101][101],jul[101][101];
char q[10000][2];

int main()
{
 ifstream fin("rj.in");
 memset(rom,0,sizeof(rom));
 memset(jul,0,sizeof(jul));
 int n,m,ir,jr,ij,jj,i,j;
 fin>>n>>m;
 fin.get();
 char c;
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=m;j++)
    {
     c=fin.get();
     if(c=='X') rom[i][j]=jul[i][j]=-1;
     else if(c=='R') {ir=i;jr=j;}
	  else if(c=='J') {ij=i;jj=j;}
    }
  fin.get();
 }
 int di[8]={-1,-1,-1, 0, 0, 1,1,1},
     dj[8]={-1, 0, 1,-1, 1,-1,0,1};
 int k,pq=1,uq=1,l,inew,jnew;
 rom[ir][jr]=1;
 q[1][0]=ir;
 q[1][1]=jr;
 while(pq<=uq)//kt timp am elem. in coada
 {//scot elem. crt din coada:
  i=q[pq][0];j=q[pq++][1];
  //vad unde pot mere din i,j shi ii pun in coada pe-aia, marcind shi in matr.
  k=rom[i][j];
  for(l=0;l<=7;l++)
    {
     inew=i+di[l];
     jnew=j+dj[l];
     if(inew>=1&&inew<=n&&jnew>=1&&jnew<=m&&rom[inew][jnew]==0)
	{
	 rom[inew][jnew]=k+1;
	 q[++uq][0]=inew;
	 q[uq][1]=jnew;
	}
    }
 }
 //la fel pt. juliette:
 pq=uq=1;
 jul[ij][jj]=1;
 q[1][0]=ij;
 q[1][1]=jj;
 while(pq<=uq)//kt timp am elem. in coada
 {//scot elem. crt din coada:
  i=q[pq][0];j=q[pq++][1];
  //vad unde pot mere din i,j shi ii pun in coada pe-aia, marcind shi in matr.
  k=jul[i][j];
  for(l=0;l<=7;l++)
    {
     inew=i+di[l];
     jnew=j+dj[l];
     if(inew>=1&&inew<=n&&jnew>=1&&jnew<=m&&jul[inew][jnew]==0)
	{
	 jul[inew][jnew]=k+1;
	 q[++uq][0]=inew;
	 q[uq][1]=jnew;
	}
    }
 }
 fin.close();
//comparam matricele:
 int lmin=10000,imin,jmin;
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    if(rom[i][j]>0&&rom[i][j]==jul[i][j])
	     if(rom[i][j]<lmin)
		    lmin=rom[imin=i][jmin=j];
 ofstream fout("rj.out");
 fout<<lmin<<" "<<imin<<" "<<jmin;
 fout.close();
return 0;
}