Cod sursa(job #1922319)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 10 martie 2017 16:58:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
#define INF 2140000000
#define MaxN 105
using namespace std;
   
FILE*IN,*OUT;
int Min=INF,PX,PY,N,M,R[MaxN][MaxN],J[MaxN][MaxN];
char Mat[MaxN][MaxN];
queue <pair<int,int> >Q1,Q2;
void Romeo()
{
	int X,Y;
	while(!Q1.empty())
	{
		X=Q1.front().first;
		Y=Q1.front().second;
		Q1.pop();
		if(X>1&&R[X-1][Y]>R[X][Y]+1)
            R[X-1][Y]=R[X][Y]+1,Q1.push(make_pair(X-1,Y));
        if(Y>1&&R[X][Y-1]>R[X][Y]+1)
            R[X][Y-1]=R[X][Y]+1,Q1.push(make_pair(X,Y-1));
        if(X<N&&R[X+1][Y]>R[X][Y]+1)
            R[X+1][Y]=R[X][Y]+1,Q1.push(make_pair(X+1,Y));
        if(Y<M&&R[X][Y+1]>R[X][Y]+1)
            R[X][Y+1]=R[X][Y]+1,Q1.push(make_pair(X,Y+1));
		if(X>1&&Y>1&&R[X-1][Y-1]>R[X][Y]+1)
            R[X-1][Y-1]=R[X][Y]+1,Q1.push(make_pair(X-1,Y-1));
        if(Y>1&&X<N&&R[X+1][Y-1]>R[X][Y]+1)
            R[X+1][Y-1]=R[X][Y]+1,Q1.push(make_pair(X+1,Y-1));
        if(X<N&&Y<M&&R[X+1][Y+1]>R[X][Y]+1)
            R[X+1][Y+1]=R[X][Y]+1,Q1.push(make_pair(X+1,Y+1));
        if(Y<M&&X>1&&R[X-1][Y+1]>R[X][Y]+1)
            R[X-1][Y+1]=R[X][Y]+1,Q1.push(make_pair(X-1,Y+1));
	}
}
void Juliet()
{
	int X,Y;
	while(!Q2.empty())
	{
		X=Q2.front().first;
		Y=Q2.front().second;
		Q2.pop();
		if(X>1&&J[X-1][Y]>J[X][Y]+1)
            J[X-1][Y]=J[X][Y]+1,Q2.push(make_pair(X-1,Y));
        if(Y>1&&J[X][Y-1]>J[X][Y]+1)
            J[X][Y-1]=J[X][Y]+1,Q2.push(make_pair(X,Y-1));
        if(X<N&&J[X+1][Y]>J[X][Y]+1)
            J[X+1][Y]=J[X][Y]+1,Q2.push(make_pair(X+1,Y));
        if(Y<M&&J[X][Y+1]>J[X][Y]+1)
            J[X][Y+1]=J[X][Y]+1,Q2.push(make_pair(X,Y+1));
		if(X>1&&Y>1&&J[X-1][Y-1]>J[X][Y]+1)
            J[X-1][Y-1]=J[X][Y]+1,Q2.push(make_pair(X-1,Y-1));
        if(Y>1&&X<N&&J[X+1][Y-1]>J[X][Y]+1)
            J[X+1][Y-1]=J[X][Y]+1,Q2.push(make_pair(X+1,Y-1));
        if(X<N&&Y<M&&J[X+1][Y+1]>J[X][Y]+1)
            J[X+1][Y+1]=J[X][Y]+1,Q2.push(make_pair(X+1,Y+1));
        if(Y<M&&X>1&&J[X-1][Y+1]>J[X][Y]+1)
            J[X-1][Y+1]=J[X][Y]+1,Q2.push(make_pair(X-1,Y+1));
	}
}
int main()
{
    IN=fopen("rj.in","r");
    OUT=fopen("rj.out","w");
	
	fscanf(IN,"%d %d ",&N,&M);
	for(int i=1;i<=N;i++)
	{
		fgets(Mat[i]+1,MaxN,IN);
		for(int j=1;j<=M;j++)
		{
			if(Mat[i][j]==' ')
				R[i][j]=J[i][j]=INF;
			else if(Mat[i][j]=='X')
				R[i][j]=J[i][j]=-1;
			else if(Mat[i][j]=='R')
				R[i][j]=0,J[i][j]=INF,Q1.push(make_pair(i,j));
			else if(Mat[i][j]=='J')
				J[i][j]=0,R[i][j]=INF,Q2.push(make_pair(i,j));
		}
	}
	Romeo();
	Juliet();
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{
			if(Mat[i][j]=='X')continue;
			if(Min>max(R[i][j],J[i][j]))
				Min=max(R[i][j],J[i][j]),PX=i,PY=j;
		}
	fprintf(OUT,"%d %d %d",Min+1,PX,PY);
	return 0;
}