Cod sursa(job #486756)

Utilizator loginLogin Iustin Anca login Data 22 septembrie 2010 18:53:52
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
# include <fstream>
# include <iostream>
# include <queue>
# include <algorithm>
# define DIM 128
using namespace std;
int n, m, a[DIM][DIM], ris, rjs, jis, jjs, x=DIM, y=DIM;
int di[8]={-1, -1, -1, 0, 1, 1, 1, 0}, dj[8]={-1, 0, 1, 1, 1, 0, -1, -1};

void read ()
{
	ifstream fin ("rj.in");
	fin>>n>>m;
	fin.get();
	char c[DIM];
	for(int i=1;i<=n;++i)
	{
		fin.getline(c, DIM);
		for (int j=0;j<m;++j)
		{
			if (c[j]=='X')a[i][j+1]=-1;
			if (c[j]=='R')ris=i, rjs=j+1;
			if (c[j]=='J')jis=i, jjs=j+1;
		}
	}
}

int inline in_m (int i, int j)
{
	if (i && j && i<=n && j<=m && a[i][j]!=-1)return 1;
	return 0;
}

void lee ()
{
	queue <int> Qri, Qrj, Qji, Qjj;
	int ri, rj, rii, rjj, ji, jj, jii, jjj, cont=1, nr, R=1, J=1;
	Qri.push(ris);
	Qrj.push(rjs);
	Qji.push(jis);
	Qjj.push(jjs);
	a[ris][rjs]=1;
	a[jis][jjs]=1;
	while (Qri.size() && Qrj.size() && cont)
	{
		nr=R;R=0;
		while (nr)
		{
			--nr;
			ri=Qri.front();Qri.pop();
			rj=Qrj.front();Qrj.pop();
			for(int k=0;k<8;++k)
			{
				rii=ri+di[k];
				rjj=rj+dj[k];
				if (in_m(rii, rjj) && a[rii][rjj]==0)
				{
					a[rii][rjj]=a[ri][rj]+1;
					Qri.push(rii);
					Qrj.push(rjj);
					++R;
				}
			}
		}
		nr=J;J=0;
		while (nr)
		{
			--nr;
			ji=Qji.front();Qji.pop();
			jj=Qjj.front();Qjj.pop();			
			for(int k=0;k<8;++k)
			{
				jii=ji+di[k];
				jjj=jj+dj[k];
				if (in_m(jii, jjj))
				{
					if (a[jii][jjj]==a[ji][jj]+1 && (jii<x || (jii==x && jjj<y)))
					{
						x=jii;y=jjj;
						cont=0;
					}
					else if (a[jii][jjj]==0)
					{
						a[jii][jjj]=a[ji][jj]+1;
						Qji.push(jii);
						Qjj.push(jjj);
						++J;
					}
				}
			}	
		}
	}
}
	
int main ()
{
	read ();
	lee();
	
	ofstream fout ("rj.out");
	fout<<a[x][y]<<" "<<x<<" "<<y;
	
	return 0;
}