Cod sursa(job #577321)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 10 aprilie 2011 01:03:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.62 kb
#include <fstream>

using namespace std;

short a[110][110], n, m, b[110][110], c[110][110], n1, m1, xr, yr, xj, yj, xf, yf=32000, tmin=32000;
char s[110];

struct Coada
{
	int x, y;
};
Coada coada[100010];

void Romeo ()
{
	int x, y, st, dr, w;
	x=xr;
	y=yr;
	st=0;
	dr=0;
	if (a[x-1][y]==0)
	{
		b[x-1][y]=1;
		coada[dr].x=x-1;
		coada[dr++].y=y;
	}
	if (a[x-1][y+1]==0)
	{
		b[x-1][y+1]=1;
		coada[dr].x=x-1;
		coada[dr++].y=y+1;
	}
	if (a[x][y+1]==0)
	{
		b[x][y+1]=1;
		coada[dr].x=x;
		coada[dr++].y=y+1;
	}
	if (a[x+1][y+1]==0)
	{
		b[x+1][y+1]=1;
		coada[dr].x=x+1;
		coada[dr++].y=y+1;
	}
	if (a[x+1][y]==0)
	{
		b[x+1][y]=1;
		coada[dr].x=x+1;
		coada[dr++].y=y;
	}
	if (a[x+1][y-1]==0)
	{
		b[x+1][y-1]=1;
		coada[dr].x=x+1;
		coada[dr++].y=y-1;
	}
	if (a[x][y-1]==0)
	{
		b[x][y-1]=1;
		coada[dr].x=x;
		coada[dr++].y=y-1;
	}
	if (a[x-1][y-1]==0)
	{
		b[x-1][y-1]=1;
		coada[dr].x=x-1;
		coada[dr++].y=y-1;
	}
	while (st<dr)
	{
		x=coada[st].x;
		y=coada[st].y;
		w=b[x][y];
		if (a[x-1][y]==0 && b[x-1][y]==0)
		{
			b[x-1][y]=w+1;
			coada[dr].x=x-1;
			coada[dr++].y=y;
		}
		if (a[x-1][y+1]==0 && b[x-1][y+1]==0)
		{
			b[x-1][y+1]=1+w;
			coada[dr].x=x-1;
			coada[dr++].y=y+1;
		}
		if (a[x][y+1]==0 && b[x][y+1]==0)
		{
			b[x][y+1]=1+w;
			coada[dr].x=x;
			coada[dr++].y=y+1;
		}
		if (a[x+1][y+1]==0 && b[x+1][y+1]==0)
		{
			b[x+1][y+1]=w+1;
			coada[dr].x=x+1;
			coada[dr++].y=y+1;
		}
		if (a[x+1][y]==0 && b[x+1][y]==0)
		{
			b[x+1][y]=w+1;
			coada[dr].x=x+1;
			coada[dr++].y=y;
		}
		if (a[x+1][y-1]==0 && b[x+1][y-1]==0)
		{
			b[x+1][y-1]=w+1;
			coada[dr].x=x+1;
			coada[dr++].y=y-1;
		}
		if (a[x][y-1]==0 && b[x][y-1]==0)
		{
			b[x][y-1]=w+1;
			coada[dr].x=x;
			coada[dr++].y=y-1;
		}
		if (a[x-1][y-1]==0 && b[x-1][y-1]==0)
		{
			b[x-1][y-1]=w+1;
			coada[dr].x=x-1;
			coada[dr++].y=y-1;
		}
		st++;
	}
}

void Julieta ()
{
	int x, y, st, dr, w;
	x=xj;
	y=yj;
	st=0;
	dr=0;
	if (a[x-1][y]==0)
	{
		c[x-1][y]=1;
		coada[dr].x=x-1;
		coada[dr++].y=y;
	}
	if (a[x-1][y+1]==0)
	{
		c[x-1][y+1]=1;
		coada[dr].x=x-1;
		coada[dr++].y=y+1;
	}
	if (a[x][y+1]==0)
	{
		c[x][y+1]=1;
		coada[dr].x=x;
		coada[dr++].y=y+1;
	}
	if (a[x+1][y+1]==0)
	{
		c[x+1][y+1]=1;
		coada[dr].x=x+1;
		coada[dr++].y=y+1;
	}
	if (a[x+1][y]==0)
	{
		c[x+1][y]=1;
		coada[dr].x=x+1;
		coada[dr++].y=y;
	}
	if (a[x+1][y-1]==0)
	{
		c[x+1][y-1]=1;
		coada[dr].x=x+1;
		coada[dr++].y=y-1;
	}
	if (a[x][y-1]==0)
	{
		c[x][y-1]=1;
		coada[dr].x=x;
		coada[dr++].y=y-1;
	}
	if (a[x-1][y-1]==0)
	{
		c[x-1][y-1]=1;
		coada[dr].x=x-1;
		coada[dr++].y=y-1;
	}
		while (st<dr)
	{
		x=coada[st].x;
		y=coada[st].y;
		w=c[x][y];
		if (a[x-1][y]==0 && c[x-1][y]==0)
		{
			c[x-1][y]=w+1;
			coada[dr].x=x-1;
			coada[dr++].y=y;
		}
		if (a[x-1][y+1]==0 && c[x-1][y+1]==0)
		{
			c[x-1][y+1]=1+w;
			coada[dr].x=x-1;
			coada[dr++].y=y+1;
		}
		if (a[x][y+1]==0 && c[x][y+1]==0)
		{
			c[x][y+1]=1+w;
			coada[dr].x=x;
			coada[dr++].y=y+1;
		}
		if (a[x+1][y+1]==0 && c[x+1][y+1]==0)
		{
			c[x+1][y+1]=w+1;
			coada[dr].x=x+1;
			coada[dr++].y=y+1;
		}
		if (a[x+1][y]==0 && c[x+1][y]==0)
		{
			c[x+1][y]=w+1;
			coada[dr].x=x+1;
			coada[dr++].y=y;
		}
		if (a[x+1][y-1]==0 && c[x+1][y-1]==0)
		{
			c[x+1][y-1]=w+1;
			coada[dr].x=x+1;
			coada[dr++].y=y-1;
		}
		if (a[x][y-1]==0 && c[x][y-1]==0)
		{
			c[x][y-1]=w+1;
			coada[dr].x=x;
			coada[dr++].y=y-1;
		}
		if (a[x-1][y-1]==0 && c[x-1][y-1]==0)
		{
			c[x-1][y-1]=w+1;
			coada[dr].x=x-1;
			coada[dr++].y=y-1;
		}
		st++;
	}
}

void Suprapunere ()
{
	int i, j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (b[i][j]==c[i][j] && b[i][j]!=0)
				if (b[i][j]<tmin)
				{
					if (j<yf)
					{
						tmin=b[i][j];
						xf=i;
						yf=j;
					}
					
				}
}

int main ()
{
	ifstream f("rj.in");
	f>>n>>m;
	int i, j;
	char ch;
	f.get();
	for (i=1; i<=n; i++)
	{
		f.get (s, 110);
		for (j=1; j<=m; j++)
		{
			ch=s[j-1];
			if (ch!='R' && ch!='J')
				if (ch==' ')
					a[i][j]=0;
				else
					a[i][j]=1;
			else
				if (ch=='R')
				{
					a[i][j]=2;
					xr=i;
					yr=j;
				}
				else
				{
					xj=i;
					yj=j;
					a[i][j]=3;
				}
		}
		f.get();
	}
	f.close();
	
	n1=n+1;
	m1=m+1;
	for (i=0; i<=n1; i++)
	{
		a[i][0]=-14;
		a[i][m1]=-14;
	}
	for (i=0; i<=m1; i++)
	{
		a[0][i]=-14;
		a[n1][i]=-14;
	}
	
	Romeo ();
	Julieta ();

	
	Suprapunere ();
	
	ofstream g("rj.out");
	g<<tmin+1<<" "<<xf<<" "<<yf<<"\n";
	g.close();
	
	return 0;
}