Cod sursa(job #428333)

Utilizator lunat1cHobinca Bogdan lunat1c Data 29 martie 2010 10:08:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
/*
rj.in
5 8
XXR XXX
 X  X X
J  X  XX
    XX
XXX XXXX

rj.out
4 4 4
tmin x y

cr : (1,3) (2,4) (3,5) (4,4)
cj : (3,1) (4,2) (4,3) (4,4)

n,m<=100


5 5
R XX
X X X
X XXX
X X X
X J X

3 3 2

cr : (1,1) (2,2) (3,2)
cj : (5,3) (4,2) (3,2)


    x-1, y-1      x-1,y        x-1,y+1
    x  , y-1       x,y         x  ,y+1
    x+1, y-1      x+1,y        x+1,y+1

*/

#include<fstream.h>
#define Max 50
int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[8]={0, 1, 1, 1, 0, -1, -1, -1};
//int dx[4]={-1,0, 1, 0}, dy[4]={0, 1, 0, -1};
char l[Max][Max];
int n, m, Rx, Ry, Jx, Jy;
int R[Max][Max], J[Max][Max];


void citire()
{
	char ch;
	int i, j;
	ifstream in("rj1.in");
	in>>n>>m;
	in.get(ch);
	for(i=1; i<=n; i++)
	   {

		for(j=1; j<=m; j++)
		{
			in.get(ch);
			l[i][j]=ch;
			if(ch=='R') {
				      Rx=i;
				      Ry=j;
				      }
			if(ch=='J') {
				      Jx=i;
				      Jy=j;
					}
		}
	     in.get(ch);
	    }
}


void afis_l()
{
    for(int i=1; i<=n; i++)
    {
	for(int j=1; j<=m; j++)
		cout<<l[i][j];
	cout<<endl;
    }
}

int interior(int x, int y)
{
	return (x>=1 && x<=n && y>=1 && y<=m);
}


void parcurgere(int x, int y, int M[Max][Max])
{
    typedef struct
    {
	int x, y;
    }Coada;
    Coada c[Max*Max];
    int p, u, i, X, Y;
    p=u=1;
    c[u].x=x;
    c[u].y=y;
    while(p<=u)
    {
       for(i=0; i<8; i++)
       {
	      X=c[p].x+dx[i];
	      Y=c[p].y+dy[i];
	      if(interior(X, Y)&& l[X][Y]==' ' && M[X][Y]==0)
	      {
		u++;
		c[u].x=X;
		c[u].y=Y;
		M[X][Y]=M[c[p].x][c[p].y]+1;
	      }
       }
       p++;
    }
}



void afis()
{
	int min, px, py, i, j;
	min=Max*Max;
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(R[i][j]==J[i][j] && R[i][j]<min && R[i][j]>0)
			{
				min=R[i][j];
				px=i;
				py=j;
			}
	ofstream out("rj.out");
	if(min==Max*Max) out<<"Fara solutie";
	else out<<min-1<<" "<<px<<" "<<py;
	out.close();


}



int main()
{
	citire();
	R[Rx][Ry]=1;
	parcurgere(Rx, Ry, R);
	J[Jx][Jy]=1;
	parcurgere(Jx, Jy, J);
	afis();
	return 0;
}