Cod sursa(job #687385)

Utilizator tanduraDomnita Dan tandura Data 22 februarie 2012 12:58:18
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include<fstream>
#include<iomanip>
using namespace std;

int n,m;
int xi[]={-1, 0, 1, 0,-1,-1, 1, 1};
int xj[]={ 0, 1, 0,-1,-1, 1, 1,-1};
int romt[157][157],jult[157][157],harta[157][157];
struct {int i; int j; int t;} x[2000],aux;
struct {int ii; int jj;} C[3000],aux1;

void read_data()
{int i,j;
 char s[256];
ifstream g("rj.in");
g>>n>>m;
g.getline(s,m+1);
for(i=1;i<=n;i++)
	{g.getline(s,m+1);
     for(j=1;j<=m;j++)
	   {if(s[j-1]=='X')
		   harta[i][j]=-1;
	   if(s[j-1]==' ')
		  harta[i][j]=0;
	   if(s[j-1]=='R')
		   harta[i][j]=1;
	   if(s[j-1]=='J')
		   harta[i][j]=2;
	   }
	}
g.close();
}

int check(int a,int b)
{int v;
	if((a>0)&&(b>0)&&(a<=n)&&(b<=m)&&(harta[a][b]==0))
		v=1;
	else
		v=0;
return v;
}

void solution()
{int i,j,ok,k,ii,jj;
 int inc,sf;
 /*for(i=1;i<=n;i++)
	 {for(j=1;j<=m;j++)
		 t<<setw(3)<<harta[i][j];
	 t<<"\n";}*/
 inc=sf=0; ok=0;
 for(i=1;((i<=n)&&(ok==0));i++)
	 for(j=1;((j<=m)&&(ok==0));j++)
		 if(harta[i][j]==1)
			 ok=1;
 romt[i-1][j-1]=1;
 C[inc].ii=i-1;
 C[inc].jj=j-1;
 while(inc<=sf)
      {aux1=C[inc++];
	   for(k=0;k<8;k++)
	      {ii=aux1.ii+xi[k];
	       jj=aux1.jj+xj[k];
		   if(check(ii,jj)==1)
			   if(romt[ii][jj]==0)
				{romt[ii][jj]=romt[aux1.ii][aux1.jj]+1;
			     sf++;
				 C[sf].ii=ii;
				 C[sf].jj=jj;
				}
		  }
	  }
 /*t<<"\n\n";
 for(i=1;i<=n;i++)
	 {for(j=1;j<=m;j++)
		 t<<setw(3)<<romt[i][j];
	 t<<"\n";}*/
 inc=sf=0; ok=0;
 for(i=1;((i<=n)&&(ok==0));i++)
	 for(j=1;((j<=m)&&(ok==0));j++)
		 if(harta[i][j]==2)
			 ok=1;
 jult[i-1][j-1]=1;
 C[inc].ii=i-1;
 C[inc].jj=j-1;
 while(inc<=sf)
      {aux1=C[inc++];
	   for(k=0;k<8;k++)
	      {ii=aux1.ii+xi[k];
	       jj=aux1.jj+xj[k];
		   if(check(ii,jj)==1)
			  if(jult[ii][jj]==0)
				{jult[ii][jj]=jult[aux1.ii][aux1.jj]+1;
			     sf++;
				 C[sf].ii=ii;
				 C[sf].jj=jj;
				}
		  }
	  }
 /*t<<"\n\n\n";
 for(i=1;i<=n;i++)
	 {for(j=1;j<=m;j++)
		 t<<setw(3)<<jult[i][j];
	 t<<"\n";}
 t<<"\n\n";*/
 k=0;
 for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
		 if((romt[i][j]==jult[i][j])&&(romt[i][j]!=0))
		   {k++;
		    x[k].i=i;
			x[k].j=j;
			x[k].t=romt[i][j];}
 aux=x[1];
 for(i=2;i<=k;i++)
	{if(aux.t>x[i].t)
		 aux=x[i];
	 if((aux.t==x[i].t)&&(aux.i>x[i].i))
		 aux=x[i];
	 if((aux.t==x[i].t)&&(aux.i==x[i].i)&&(aux.j>x[i].j))
		 aux=x[i];
	}
 
}

void display()
{ofstream t("rj.out");
 t<<aux.t<<" "<<aux.i<<" "<<aux.j;
t.close();
}

int main()
{
read_data();
solution();
display();
return 0;
}