Cod sursa(job #1912251)

Utilizator adu18sptAndrei Mircea adu18spt Data 8 martie 2017 00:18:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<fstream>
#include<queue>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int n,m,map1[101][101],map2[101][101];
char v[101];
int xr,yr,xj,yj;
int di[9]={0,0,1,-1,1,-1,1,-1};
int dj[9]={1,-1,0,0,1,-1,-1,1};

queue < pair <int,int> > coada1;
queue < pair <int,int> > coada2;

int x,y,minim=100000;

void Read()
{
	fin>>n>>m;
	
	for(int i=1;i<=n;i++)
	{
		fin.get();
  		fin.get(v,101);
		for(int j=0;j<m;j++)
		{
			
			if(v[j]==' ')
			{
				map1[i][j+1]=0;
				map2[i][j+1]=0;
			}
			if(v[j]=='X')
			{
				map1[i][j+1]=-1;
				map2[i][j+1]=-1;
			}
			if(v[j]=='R')
			{
				map1[i][j+1]=1;
				map2[i][j+1]=1;
				xr=i;
				yr=j+1;
			}
			if(v[j]=='J')
			{
				map1[i][j+1]=1;
				map2[i][j+1]=1;
				xj=i;
				yj=j+1;
			}
		}
	}
	
}

bool OK1(int i,int j)
{
	if(i<1 || j<1 || i>n || j>m)
    return false;
    if(map1[i][j]==-1)
    return false;
     
    return true;
}

bool OK2(int i,int j)
{
	if(i<1 || j<1 || i>n || j>m)
    return false;
    if(map2[i][j]==-1)
    return false;
     
    return true;
}

void LeeR()
{
	int next_i,next_j;
	int i,j;
	coada1.push(make_pair(xr,yr));
	map1[xr][yr]=1;
	
	while(!coada1.empty())
	{
		i=coada1.front().first;
		j=coada1.front().second;
		
		coada1.pop();
		
		for(int dir=0;dir<8;dir++)
		{
			next_i=i+di[dir];
			next_j=j+dj[dir];
			
			if(OK1(next_i,next_j) && map1[next_i][next_j]<1)
			{
				map1[next_i][next_j]=map1[i][j]+1;
				coada1.push(make_pair(next_i,next_j));
			}
			
		}
		
		
	}
	
	
}

void LeeJ()
{
	int next_i,next_j;
	int i,j;
	coada2.push(make_pair(xj,yj));
	map2[xj][yj]=1;
	
	while(!coada2.empty())
	{
		i=coada2.front().first;
		j=coada2.front().second;
		
		coada2.pop();
		
		for(int dir=0;dir<8;dir++)
		{
			next_i=i+di[dir];
			next_j=j+dj[dir];
			
			if(OK2(next_i,next_j) && map2[next_i][next_j]<1)
			{
				map2[next_i][next_j]=map2[i][j]+1;
				coada2.push(make_pair(next_i,next_j));
			}
			
		}
		
		
	}
	
	
}


void Solve()
{
	LeeR();
	LeeJ();
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if((map1[i][j]==map2[i][j])&&(map1[i][j]>1))	
			{
				if(map1[i][j]<minim)
				{
					minim=map1[i][j]-1;
					x=i;
					y=j;
				}
			}
		}
	}
	
	
}

int main()
{
	Read();
	Solve();
	fout<<x<<" "<<y<<" "<<minim+1;
	
	return 0;
}