Cod sursa(job #442945)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 15 aprilie 2010 18:56:10
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include<iostream.h>
#include<fstream.h>

ifstream f("rj.in");
ofstream g("rj.out");

struct coada
{
	int c[10100];
};

coada v[6];

char a[200][200],ok1='1';
int n,m,i,j,poz=0,min,p1,sfc,p2;
int b[200][200],w[200][200];

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

void lee()
{
	int inc;
	inc=1;
	sfc=1;
	a[v[poz].c[inc]][v[poz+1].c[inc]]=ok1;
	while (inc<=sfc)
	{
		if (a[v[poz].c[inc]-1][v[poz+1].c[inc]-1]!='X'&&a[v[poz].c[inc]-1][v[poz+1].c[inc]-1]!=ok1) //stanga-sus
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc]-1;
			v[poz+1].c[sfc]=v[poz+1].c[inc]-1;
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]-1][v[poz+1].c[inc]-1]=ok1;
		}
		
		if (a[v[poz].c[inc]-1][v[poz+1].c[inc]+1]!='X'&&a[v[poz].c[inc]-1][v[poz+1].c[inc]+1]!=ok1) //dreapta-sus
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc]-1;
			v[poz+1].c[sfc]=v[poz+1].c[inc]+1;
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]-1][v[poz+1].c[inc]+1]=ok1;
		}
		
		if (a[v[poz].c[inc]][v[poz+1].c[inc]-1]!='X'&&a[v[poz].c[inc]][v[poz+1].c[inc]-1]!=ok1) //stanga
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc];
			v[poz+1].c[sfc]=v[poz+1].c[inc]-1;
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]][v[poz+1].c[inc]-1]=ok1;
		}
		if (a[v[poz].c[inc]][v[poz+1].c[inc]+1]!='X'&&a[v[poz].c[inc]][v[poz+1].c[inc]+1]!=ok1)  //dreapta
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc];
			v[poz+1].c[sfc]=v[poz+1].c[inc]+1;
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]][v[poz+1].c[inc]+1]=ok1;
		}
		if (a[v[poz].c[inc]+1][v[poz+1].c[inc]]!='X'&&a[v[poz].c[inc]+1][v[poz+1].c[inc]]!=ok1)	//jos
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc]+1;
			v[poz+1].c[sfc]=v[poz+1].c[inc];
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]+1][v[poz+1].c[inc]]=ok1;
		}
		
		if (a[v[poz].c[inc]+1][v[poz+1].c[inc]-1]!='X'&&a[v[poz].c[inc]+1][v[poz+1].c[inc]-1]!=ok1)	//jos-stanga
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc]+1;
			v[poz+1].c[sfc]=v[poz+1].c[inc]-1;
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]+1][v[poz+1].c[inc]-1]=ok1;
		}
		
		if (a[v[poz].c[inc]+1][v[poz+1].c[inc]+1]!='X'&&a[v[poz].c[inc]+1][v[poz+1].c[inc]+1]!=ok1)	//jos-dreapta
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc]+1;
			v[poz+1].c[sfc]=v[poz+1].c[inc]+1;
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]+1][v[poz+1].c[inc]+1]=ok1;
		}
		
		if (a[v[poz].c[inc]-1][v[poz+1].c[inc]]!='X'&&a[v[poz].c[inc]-1][v[poz+1].c[inc]]!=ok1) //sus
		{
			sfc++;
			v[poz].c[sfc]=v[poz].c[inc]-1;
			v[poz+1].c[sfc]=v[poz+1].c[inc];
			v[poz+2].c[sfc]=v[poz+2].c[inc]+1;
			a[v[poz].c[inc]-1][v[poz+1].c[inc]]=ok1;
		}
		inc++;
	}
}

int main()
{
	f>>n>>m;
	f.get();
	obstacol();
	for (i=1;i<=n;f.get(),++i)
		for (j=1;j<=m;++j)
		{
			f.get(a[i][j]);
			if (a[i][j]=='J')
			{
				v[0].c[1]=i;
				v[1].c[1]=j;
				v[2].c[1]=1;
				a[i][j]='1';
			}
			else if (a[i][j]=='R')
			{
				v[3].c[1]=i;
				v[4].c[1]=j;
				v[5].c[1]=1;
				a[i][j]='2';
			}
		}
	lee();
	poz=3;
	ok1++;
	lee();
	min=31999; p1=0; p2=0;
	/*for (i=1;i<=sfc;++i)
		for (j=1;j<=sfc;++j)
		if (v[0].c[i]==v[3].c[j]&&v[1].c[i]==v[4].c[j]&&v[2].c[i]==v[5].c[j]&&v[5].c[j]<min) 
		{min=v[5].c[i]; p1=v[0].c[i]; p2=v[1].c[i];}
	*/
	for (i=1;i<=sfc;++i)
	{
			w[v[0].c[i]][v[1].c[i]]=v[2].c[i];
			b[v[3].c[i]][v[4].c[i]]=v[5].c[i];
	}
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (a[i][j]=='X') w[i][j]=b[i][j]=-1;
	int qq=1;
	for (i=1;i<=n&&qq==1;++i)
		for (j=1;j<=m;++j)
			if (w[i][j]==b[i][j])
				if (w[i][j]>0&&w[i][j]<min) {p1=i; p2=j; min=w[i][j]; }
			g<<min<<' '<<p1<<' '<<p2;
	f.close();
	g.close();
	return 0;
}