Cod sursa(job #530445)

Utilizator Raul_NistorNistor Raul Raul_Nistor Data 7 februarie 2011 19:52:42
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.1 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int a[102][102],optr[102][102],optj[102][102],n,m,i,j,istr,istj,jstr,jstj,x,y,tmin=1000000;
queue<int>qxr,qyr,qxj,qyj;
void citire()
{
	int i,j;
	char buf[200];
	f>>n>>m;
	f.getline(buf,102);
	for(i=1;i<=n;i++)
		{
			f.getline(buf,114);
			for (j=0;j<m;j++)
			{
				if (buf[j]=='X') a[i][j+1]=1;
				if (buf[j]=='R') a[i][j+1]=2;
				if (buf[j]=='J') a[i][j+1]=3;
			}
		}
}
int main()
{
	citire();
/*	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			cout << a[i][j] << " ";
		cout << '\n';
	}
*/	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]==2)
			{
				istr=i;
				jstr=j;
			}
			else
				if(a[i][j]==3)
				{
					istj=i;
					jstj=j;
				}
	for(i=0;i<=m+1;i++)
		a[0][i]=a[n+1][i]=1;
	for(i=1;i<=n-1;i++)
		a[i][0]=a[i][m+1]=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			optr[i][j]=n*m+1;
	optr[istr][jstr]=1;
	qxr.push(istr);
	qyr.push(jstr);
	while(!qxr.empty())
	{
		int ic,jc,iv,jv;
		ic=qxr.front();
		jc=qyr.front();
		qxr.pop();
		qyr.pop();
		iv=ic+1;jv=jc;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic-1;jv=jc;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic;jv=jc+1;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic;jv=jc-1;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic-1;jv=jc-1;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic-1;jv=jc+1;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic+1;jv=jc-1;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
		iv=ic+1;jv=jc+1;
		if(a[iv][jv]==0)
			if(optr[ic][jc]+1<optr[iv][jv])
			{
				optr[iv][jv]=optr[ic][jc]+1;
				qxr.push(iv);
				qyr.push(jv);
			}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			optj[i][j]=n*m+1;
	optj[istj][jstj]=1;
	qxj.push(istj);
	qyj.push(jstj);
	while(!qxj.empty())
	{
		int ic,jc,iv,jv;
		ic=qxj.front();
		jc=qyj.front();
		qxj.pop();
		qyj.pop();
		iv=ic+1;jv=jc;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic-1;jv=jc;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic;jv=jc+1;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic;jv=jc-1;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic-1;jv=jc-1;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic-1;jv=jc+1;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic+1;jv=jc-1;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
		iv=ic+1;jv=jc+1;
		if(a[iv][jv]==0)
			if(optj[ic][jc]+1<optj[iv][jv])
			{
				optj[iv][jv]=optj[ic][jc]+1;
				qxj.push(iv);
				qyj.push(jv);
			}
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(optr[i][j]==optj[i][j]&&optr[i][j]<tmin)
			{
				tmin=optr[i][j];
				x=i;
				y=j;
			}
	cout<<tmin<<' '<<x<<' '<<y;
	g<<tmin<<' '<<x<<' '<<y<<'\n';
	return 0;
}
/*
5 5
R XX 
X X X
X XXX 
X X X
X J X
*/