Cod sursa(job #412546)

Utilizator deeprogressmelnic vlad deeprogress Data 5 martie 2010 20:00:26
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
# include <fstream.h>
# include <iostream.h>
struct punct{int c,r,j;};
struct x{int i,j;};
char s[101];
int i,j,n,m,xj,yj,xr,yr,ii,jj,u,p,k,inou,jnou,min;
punct M[101][101];
ifstream f("rj.in");
ofstream g("rj.out");
int di[]={0, 1, 0, -1, -1, 1, -1, 1},dj[]={1, 0, -1, 0, -1, 1,  1,-1};
x C[10002];

int valid (int i, int j)
{ if(i<=n && i>=1 && j>=1 && j<=m &&  M[i][j].c!=1) return 1;
  return 0;
}

int main()
{ f>>n>>m;
  for(i=0;i<=n;i++) 
	 {f.getline(s,101);
      for(j=0;j<m;j++) { if(s[j]=='X') M[i][j+1].c=1;
	                     else if(s[j]=='R') {xr=i;yr=j+1;} else  if(s[j]=='J'){xj=i;yj=j+1;}
	  }
	 } 
	
  
  // parcurg Romeo
  p=u=1;
  C[1].i=xr;C[1].j=yr; M[xr][yr].r=2;
  while(p<=u) { // etchetez punctele din C[p]
	            ii=C[p].i; jj=C[p].j;
                for(k=0;k<=7;k++) { inou=ii+di[k], jnou=jj+dj[k];
                                    if(valid(inou, jnou) && M[inou][jnou].r==0)
									      { u++;C[u].i=inou;C[u].j=jnou;M[inou][jnou].r=M[ii][jj].r+1;}
                         										  
				                   }
				p++;}
  
  
 
  p=u=1;
  C[1].i=xj;C[1].j=yj; M[xj][yj].j=2;
  while(p<=u) { // etchetez punctele din C[p]
	            ii=C[p].i; jj=C[p].j;
                for(k=0;k<=7;k++) { inou=ii+di[k], jnou=jj+dj[k];
                                    if(valid(inou, jnou)&& M[inou][jnou].j==0)
									      { u++;C[u].i=inou;C[u].j=jnou;M[inou][jnou].j=M[ii][jj].j+1;}
                         										  
				                   }
				p++;}
  
  
// vezi unde se intalnesc
  jj=101;
  min=10002;
  for(i=1;i<=n;i++) 
	   for(j=1;j<=m;j++) if(M[i][j].r && M[i][j].r==M[i][j].j)
	                                        if(M[i][j].r<min || M[i][j].r==min && (i<ii || i==ii && j<jj)) 
											          {min=M[i][j].r;ii=i;jj=j;}
											    
   g<<min-1<<' '<<ii<<' '<<jj<<'\n';
    
  
  f.close();g.close();
    return 0;
}