Cod sursa(job #819818)

Utilizator avramavram andrei marius avram Data 19 noiembrie 2012 18:59:36
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int dx[9]={0, 0, 1, 1, 1, 0, -1, -1, -1};
int dy[9]={0, 1, 1, 0, -1, -1, -1, 0, 1};
int a[110][150], b[110][110], n, m, i, j, ok, p, u, ri, rj, ji, jj, ic, jc, iv, jv, c[2][10010], d[2][10010], minim, linie, coloana;
char s[110];
int main(){
	f>>n>>m;
	for(i=1; i<=n; i++)
	{
		f.get();
		f.get(s+1, 110);
		for(j=1; j<=m; j++)
		{
			if(s[j]=='R')
			{
				ri=i;
				rj=j;
				a[i][j]=-1;
				b[i][j]=-1;
			}
			else if(s[j]=='J')
			{
				ji=i;
				jj=j;
				a[i][j]=-2;
				b[i][j]=-2;
			}
			else if(s[j]=='X')
			{
				a[i][j]=-3;
				b[i][j]=-3;
			}
		}
	}
	f.close();
	p=u=1;
	ok=0;
	c[0][u]=ri;
	c[1][u]=rj;
	a[ri][rj]=1;
	while(p<=u && ok==0)
	{
		ic=c[0][p];
		jc=c[1][p];
		for(i=1; i<=8; i++)
		{
			iv=ic+dx[i];
			jv=jc+dy[i];
			if(iv>=1 && iv<=n && jv>=1 && jv<=m && ( a[iv][jv]==0 || a[iv][jv]==-1 || a[iv][jv]==-2) )
			{
				a[iv][jv]=a[ic][jc]+1;
				u++;
				c[0][u]=iv;
				c[1][u]=jv;
				if(iv==ji && jv==jj)
					ok=1;
			}
		}
		p++;
	}
	p=u=1;
	ok=0;
	d[0][u]=ji;
	d[1][u]=jj;
	b[ji][jj]=1;
	while(p<=u && ok==0)
	{
		ic=d[0][p];
		jc=d[1][p];
		for(i=1; i<=8; i++)
		{
			iv=ic+dx[i];
			jv=jc+dy[i];
			if(iv>=1 && iv<=n && jv>=1 && jv<=m && ( b[iv][jv]==0 || b[iv][jv]==-1 || b[iv][jv]==-2) )
			{
				b[iv][jv]=b[ic][jc]+1;
				u++;
				d[0][u]=iv;
				d[1][u]=jv;
				if(iv==ri && jv==rj)
					ok=1;
			}
		}
		p++;
	}
	ok=0;
	minim=999999999;
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(a[i][j]==b[i][j] && a[i][j]>0 && b[i][j]>0)
			{
				if(minim>a[i][j])
				{
					minim=a[i][j];
					linie=i;
					coloana=j;
				}
			}
	g<<minim<<' '<<linie<<' '<<coloana<<"\n";
	g.close();
	return 0;
}