Cod sursa(job #691679)

Utilizator emle98Emanuel Silivasan emle98 Data 26 februarie 2012 12:37:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;

int a[111][111];
int ro[111][111];
int jo[111][111];
int main()
{
	queue <int> xr,yr,xj,yj;
	ifstream fin("rj.in");
	int n,m,i,p;
	//int xr,yr,xj,yj;
	string buff;
	fin>>n>>m; getline(fin,buff);
	for(i=0;i<=n+1;i++)
	{
		for(p=0;p<=m+1;p++)
		{
			ro[i][p]=n*m+1, jo[i][p]=n*m+1;
			if(i==0 || i==n+1 || p==0 || p==m+1) a[i][p]=-1;
		}
	}
	for(i=1;i<=n;i++)
	{
			getline(fin,buff);
			cout<<buff<<endl;
			for(p=1;p<=m;p++)
			{
				if(buff[p-1]=='X') a[i][p]=1;
				else if(buff[p-1]==' ') a[i][p]=0;
				else if(buff[p-1]=='R') xr.push(i), yr.push(p), ro[i][p]=1;
				else if(buff[p-1]=='J') xj.push(i), yj.push(p), jo[i][p]=1;
			}
	}
	int x,y,vx,vy;
	while(!xr.empty())
	{
		x=xr.front(); xr.pop();
		y=yr.front(); yr.pop();
		vx=x+1; vy=y;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x+1; vy=y+1;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x+1; vy=y-1;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x; vy=y+1;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x; vy=y-1;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x-1; vy=y;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x-1; vy=y+1;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
		vx=x-1; vy=y-1;
		if(a[vx][vy]==0 && ro[vx][vy]>ro[x][y]+1)
		{
			ro[vx][vy]=ro[x][y]+1;
			xr.push(vx); yr.push(vy);
		}
	}		
	while(!xj.empty())
	{
		x=xj.front(); xj.pop();
		y=yj.front(); yj.pop();
		vx=x+1; vy=y;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x+1; vy=y+1;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x+1; vy=y-1;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x; vy=y+1;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x; vy=y-1;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x-1; vy=y;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x-1; vy=y+1;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
		vx=x-1; vy=y-1;
		if(a[vx][vy]==0 && jo[vx][vy]>jo[x][y]+1)
		{
			jo[vx][vy]=jo[x][y]+1;
			xj.push(vx); yj.push(vy);
		}
	}
	int tmin=0;
	for(x=1;x<=n;x++)
	{
		for(y=1;y<=m;y++)
		{
			if(ro[x][y]==jo[x][y] && a[x][y]==0 && ro[x][y]!=n*m+1)
			{				
				vx=x;
				vy=y;
				tmin=ro[x][y];
				break;
			}
		}
	}/*
	for(x=1;x<=n;x++)
	{
		for(y=1;y<=m;y++)
		{
			if(ro[x][y]<10) cout<<" ";
			cout<<" "<<ro[x][y];
		}
		cout<<"     ";
		for(y=1;y<=m;y++)
		{
			if(jo[x][y]<10) cout<<" ";
			cout<<" "<<jo[x][y];
		}
		cout<<endl;
	}*/
	ofstream fout("rj.out");
	fout<<vy<<" "<<vx<<" "<<tmin;
	return 0;
}