Cod sursa(job #409991)

Utilizator niovanIovan Alexandru niovan Data 3 martie 2010 23:14:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include<fstream>
#include<stdio.h>
#define NMax 101
#define inf 10001
using namespace std;

FILE *fin=fopen("rj.in","r");
fstream fout("rj.out",ios::out);

struct pozitie{int x,y;};
struct nod{int x,y; nod *urm;};

char b[100];
int R[NMax][NMax],J[NMax][NMax];
pozitie r,j;
nod *C_prim, *C_ultim;
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
int n,m;

void Citire()
{
	int i,k;
	char c;
	fscanf(fin,"%d %d",&n,&m);
	fscanf(fin,"%c",&c);
	for(i=1;i<=n;i++)
	{
		fgets(b,100,fin);
		for(k=1;k<=m;k++)
		{
			if(b[k-1]=='R') {r.x=i; r.y=k;}
			if(b[k-1]=='J') {j.x=i; j.y=k;}
			if(b[k-1]=='X') {R[i][k]=-1; J[i][k]=-1;}
		}
	}
}

void Romeo()
{
	int x,y,xnou,ynou,i,minim,ok=1;
	nod *p,*q;
	C_prim=C_ultim=NULL;
	p=new nod;
	p->x=r.x;
	p->y=r.y;
	p->urm=NULL;
	C_prim=C_ultim=p;
	while(C_prim!=NULL)
	{
		x=C_prim->x;
		y=C_prim->y;
		q=C_prim;
		C_prim=C_prim->urm;
		delete q;
		if(!(x==r.x&&y==r.y))
		{
			minim=inf;
			for(i=0;i<8;i++)
			{
				if(R[x+dx[i]][y+dy[i]]==0&&(x+dx[i]==r.x)&&(y+dy[i]==r.y)&&minim>R[x+dx[i]][y+dy[i]])
					minim=R[x+dx[i]][y+dy[i]];
				if(R[x+dx[i]][y+dy[i]]!=0&&R[x+dx[i]][y+dy[i]]!=-1&&minim>R[x+dx[i]][y+dy[i]]&&(x+dx[i]<=n)&&(x+dx[i]>=1)&&(y+dy[i]>=1)&&(y+dy[i]<=m))
					minim=R[x+dx[i]][y+dy[i]];
			}
			R[x][y]=minim+1;
		}
		for(i=0;i<8;i++)
		{
			xnou=x+dx[i];
			ynou=y+dy[i];
			if(xnou>=1&&xnou<=n&&ynou>=1&&ynou<=m&&R[xnou][ynou]==0&&(!(xnou==r.x&&ynou==r.y)))
				{ 
					p=new nod;
					p->x=xnou; p->y=ynou; p->urm=NULL;
					C_ultim->urm=p;
					C_ultim=C_ultim->urm;
					if(ok) {ok=0; C_prim=p;}
				}
		}
	}
}

void Julieta()
{
	int x,y,xnou,ynou,i,minim,ok=1;
	nod *p,*q;
	C_prim=C_ultim=NULL;
	p=new nod;
	p->x=j.x;
	p->y=j.y;
	p->urm=NULL;
	C_prim=C_ultim=p;
	while(C_prim!=NULL)
	{
		x=C_prim->x;
		y=C_prim->y;
		q=C_prim;
		C_prim=C_prim->urm;
		delete q;
		if(!(x==j.x&&y==j.y))
		{
			minim=inf;
			for(i=0;i<8;i++)
			{
				if(J[x+dx[i]][y+dy[i]]==0&&(x+dx[i]==j.x)&&(y+dy[i]==j.y)&&minim>J[x+dx[i]][y+dy[i]])
					minim=J[x+dx[i]][y+dy[i]];
				if(J[x+dx[i]][y+dy[i]]!=0&&J[x+dx[i]][y+dy[i]]!=-1&&minim>J[x+dx[i]][y+dy[i]]&&(x+dx[i]<=n)&&(x+dx[i]>=1)&&(y+dy[i]>=1)&&(y+dy[i]<=m))
					minim=J[x+dx[i]][y+dy[i]];
			}
			J[x][y]=minim+1;
		}
		for(i=0;i<8;i++)
		{
			xnou=x+dx[i];
			ynou=y+dy[i];
			if(xnou>=1&&xnou<=n&&ynou>=1&&ynou<=m&&J[xnou][ynou]==0&&(!(xnou==j.x&&ynou==j.y)))
				{ 
					p=new nod;
					p->x=xnou; p->y=ynou; p->urm=NULL;
					C_ultim->urm=p;
					C_ultim=C_ultim->urm;
					if(ok) {ok=0; C_prim=p;}
				}
		}
	}
}

void Solutie()
{
	pozitie sol;
	int min,i,k;
	min=inf;
	for(i=1;i<=n;i++)
		for(k=1;k<=m;k++)
			if(R[i][k]==J[i][k]&&R[i][k]<min&&R[i][k]!=-1&&R[i][k]!=0)
			{
				min=R[i][k];
				sol.x=i;
				sol.y=k;
			}
	if(min==inf) fout<<"-1";
	else
	fout<<min+1<<" "<<sol.x<<" "<<sol.y;	

}

int main()
{
	Citire();
	Romeo();
	Julieta();
	Solutie();
	return 0;
}