Cod sursa(job #412005)

Utilizator deeprogressmelnic vlad deeprogress Data 5 martie 2010 12:00:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream.h>
#include <string.h>

ifstream f("rj.in");
ofstream g("rj.out");
int di[]={-1,-1,0,+1,+1,+1,0,-1},dj[]={0,-1,-1,-1,0,+1,+1,+1};
int n,m,i,j,timp,tmin=10000,x,xi,y,xr,yr,xj,yj,x0,y0;
char s[100];
int a[100][100],pas,min;

void afis()
{
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=m;j++)
			g<<a[i][j];
		g<<'\n';
	}
	g<<'\n';
}
int valid (int i, int j)
	{
	if(i>=1 && i<=n && j<=m&& j>=1 && a[i][j]==0)
		return 1;
	return 0;
	}


void pozitie(int i, int j,int pas)
{ if(a[i][j]==pas) { x0=i;y0=j;}
     else 
		 for(int k=1;k<=8;k++)
		    {
	  	      int inou=i-di[k];
		      int jnou=j-dj[k];
			  if(i>=1 && i<=n && j<=m&& j>=1 && a[inou][jnou]==a[i][j]-1) pozitie(inou,jnou,pas);
		 }
	
}

void actualizeaza(int i, int j,int pas)
{  
	if(a[i][j]==pas) { //g<<"\n actualizare "<< i<<' '<<j<<' '<<x0<<' '<<y0<< '\n';
		               if(j<y0) {x0=i;y0=j;}
	                 }
     else 
		 for(int k=1;k<=8;k++)
		    { 
	  	      int inou=i-di[k];
		      int jnou=j-dj[k];
			  if(inou>=1 && inou<=n && jnou<=m&& jnou>=1 && a[inou][jnou]==a[i][j]-1) 
				  {//g<<"\n mrg in : "<<inou<<' '<<jnou<<'\n';
					  actualizeaza(inou,jnou,pas);
				  }
		 }
	
}


void back ( int i, int j, int pas)
	{ a[i][j]=pas;
	  if(i==xj && j==yj) { if(pas<min && pas%2!=0) { //g<<"\n acum min="<<pas<<'\n';
		                                           min=pas;pozitie(i,j,(pas+1)/2);
	                                               // g<<x0<<' '<<y0<<'\n'; 
	  }
	                           else if(pas==min) { 
								   
								                     //g<<"\n actualizare "<< i<<' '<<j<<'\n';
								                    actualizeaza(i,j,(pas+1)/2);
							                      }
						}
		else 
	      for(int k=1;k<=8;k++)
		    {
	  	      int inou=i+di[k];
		      int jnou=j+dj[k];
		      if(valid(inou,jnou))back(inou,jnou,pas+1);
			}
	a[i][j]=0;
	//afis();
}
	
int main ()
	{
	f>>n>>m;
	for(i=0;i<=n;i++)
		{ f.getline(s,100);
		   for(j=0;j<m;j++) { if(s[j]=='R') {xr=i;yr=j+1;}
		                      if(s[j]=='J') {xj=i;yj=j+1;}
							  if(s[j]=='X') a[i][j+1]=1;
		                    }
		}
	

  /*  for(i=1;i<=n;i++)
		{for(j=1;j<=m;j++)
			g<<a[i][j];
		 g<<'\n';
		}*/
		
	min=n*m;
	back(xr,yr,1);
	g<<(min)/2<<' '<<x0<<' '<<y0<<'\n';
	f.close () ;
	g.close () ;
	return 0;
	}