Cod sursa(job #351612)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 28 septembrie 2009 19:13:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#define NMax 102
#define PMax 9
#define inf NMax*NMax
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

int dx[PMax]={0, 0, 1, 0, -1, -1, 1, -1, 1};
int dy[PMax]={0, 1, 0, -1, 0, -1, 1,  1,-1};
char a[NMax][NMax];
int r[NMax][NMax],j[NMax][NMax];
struct punct { int l,c; } R,J,I; //I-intalnire
int n,m,tmin=inf;

void citire ()
{
  char c;
  f>>n>>m; f.get(c);
  for (int i=1; i<=n; i++, f.get(c))
	for (int j=1; j<=m; j++)
	{
	  f.get(c);
	  if (c=='R') { R.l=i; R.c=j; a[i][j]='X'; }
	  else if (c=='J') { J.l=i; J.c=j; a[i][j]='X'; }
	  else a[i][j]=c;
	}
  f.close ();
}

void bordare ()
{
  for (int i=0; i<=n+1; i++)  a[i][0]=a[i][m+1]='X';
  for (int i=0; i<=m+1; i++)  a[0][i]=a[n+1][i]='X';
}

void drum (punct X,int d[NMax][NMax])
{
  int i,j,inc=0,sf=0;
  punct c[NMax*NMax],p,y;
  for (i=1; i<=n; i++)
	for (j=1; j<=m; j++)
	  d[i][j]=-1;
  c[0]=X; d[c[0].l][c[0].c]=1;
  while (inc<=sf)
  {
	p=c[inc++];
	for (i=1; i<PMax; i++)
	{
	  y.l=p.l+dx[i]; y.c=p.c+dy[i];
	  if (a[y.l][y.c]==' ' && d[y.l][y.c]==-1)
	  {
		d[y.l][y.c]=d[p.l][p.c]+1;
		c[++sf]=y;
	  }
	}
  }
}

void punct_intalnire (int r[NMax][NMax],int j[NMax][NMax])
{
  for (int i=1; i<=n; i++)
	for (int k=1; k<=m; k++)
	  if (r[i][k]==j[i][k] && r[i][k]<tmin && r[i][k]!=-1)
	  {
		tmin=r[i][k];
		I.l=i; I.c=k;
	  }
}

void afisare ()
{
  g<<tmin<<" "<<(int)I.l<<" "<<(int)I.c;
  g.close ();
}

int main ()
{
  citire ();
  bordare ();
  drum (R,r);
  drum (J,j);
  punct_intalnire (r,j);
  afisare ();
  return 0;
}