Cod sursa(job #896933)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 27 februarie 2013 18:02:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.69 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

fstream f("rj.in",ios::in);
fstream g("rj.out",ios::out);

struct coord
{
	int l,c,dist;
};

coord q1[10000],q2[10000];
int a[101][101],x[101][101];
char s[101];
int n,m,i,j,nouadist,minim,minl,minc,indexcoada,lungimecoada1,lungimecoada2;



void algoritmleeromeo()
{
	coord curent;
    indexcoada=1;
	while (indexcoada<=lungimecoada1)
	{
		curent=q1[indexcoada];
		nouadist=curent.dist+1;
		if (a[curent.l][curent.c+1]==0)
		{
			lungimecoada1++;
			q1[lungimecoada1].l=curent.l;
			q1[lungimecoada1].c=curent.c+1;

	q1[lungimecoada1].dist=nouadist;
	        a[curent.l][curent.c+1]=-1;
		}
		if (a[curent.l][curent.c-1]==0)
		{
			lungimecoada1++;
	        q1[lungimecoada1].l=curent.l;
			q1[lungimecoada1].c=curent.c-1;
			q1[lungimecoada1].dist=nouadist;
			a[curent.l][curent.c-1]=-1;
		}
		if (a[curent.l+1][curent.c+1]==0)

	    {
			lungimecoada1++;
			q1[lungimecoada1].l=curent.l+1;
			q1[lungimecoada1].c=curent.c+1;
			q1[lungimecoada1].dist=nouadist;
			a[curent.l+1][curent.c+1]=-1;

	    }
		if (a[curent.l-1][curent.c+1]==0)
		{
			lungimecoada1++;
			q1[lungimecoada1].l=curent.l-1;
	        q1[lungimecoada1].c=curent.c+1;
			q1[lungimecoada1].dist=nouadist;
			a[curent.l-1][curent.c+1]=-1;
		}
		if (a[curent.l+1][curent.c-1]==0)
		{

        	lungimecoada1++;
			q1[lungimecoada1].l=curent.l+1;
			q1[lungimecoada1].c=curent.c-1;
			q1[lungimecoada1].dist=nouadist;
			a[curent.l+1][curent.c-1]=-1;
		}
		if (a[curent.l-1][curent.c-1]==0)
		{
			lungimecoada1++;
			q1[lungimecoada1].l=curent.l-1;
			q1[lungimecoada1].c=curent.c-1;
        	q1[lungimecoada1].dist=nouadist;
        	a[curent.l-1][curent.c-1]=-1;
		}
		if (a[curent.l+1][curent.c]==0)
		{
			lungimecoada1++;
	        q1[lungimecoada1].l=curent.l+1;
			q1[lungimecoada1].c=curent.c;
			q1[lungimecoada1].dist=nouadist;
			a[curent.l+1][curent.c]=-1;
		}
		if (a[curent.l-1][curent.c]==0)

	   {
			lungimecoada1++;
			q1[lungimecoada1].l=curent.l-1;
			q1[lungimecoada1].c=curent.c;
			q1[lungimecoada1].dist=nouadist;
			a[curent.l-1][curent.c]=-1;

	   }
		indexcoada++;
	}
}



void algoritmleejulieta()
{
	coord curent;
    indexcoada=1;
	while (indexcoada<=lungimecoada2)
	{

		curent=q2[indexcoada];
		nouadist=curent.dist+1;
		if (x[curent.l][curent.c+1]==0)
		{
			lungimecoada2++;
			q2[lungimecoada2].l=curent.l;
			q2[lungimecoada2].c=curent.c+1;
			q2[lungimecoada2].dist=nouadist;
			x[curent.l][curent.c+1]=-1;
		}

	if (x[curent.l][curent.c-1]==0)
		{
			lungimecoada2++;
			q2[lungimecoada2].l=curent.l;
			q2[lungimecoada2].c=curent.c-1;
	        q2[lungimecoada2].dist=nouadist;
	        x[curent.l][curent.c-1]=-1;
		}
		if (x[curent.l+1][curent.c+1]==0)
		{
			lungimecoada2++;
			q2[lungimecoada2].l=curent.l+1;
			q2[lungimecoada2].c=curent.c+1;
			q2[lungimecoada2].dist=nouadist;
			x[curent.l+1][curent.c+1]=-1;
		}
		if (x[curent.l-1][curent.c+1]==0)
		{

        	lungimecoada2++;
			q2[lungimecoada2].l=curent.l-1;
			q2[lungimecoada2].c=curent.c+1;
			q2[lungimecoada2].dist=nouadist;
			x[curent.l-1][curent.c+1]=-1;
		}
		if (x[curent.l+1][curent.c-1]==0)
		{
			lungimecoada2++;
			q2[lungimecoada2].l=curent.l+1;
			q2[lungimecoada2].c=curent.c-1;
	        q2[lungimecoada2].dist=nouadist;
	        x[curent.l+1][curent.c-1]=-1;
		}
		if (x[curent.l-1][curent.c-1]==0)
		{
			lungimecoada2++;
        	q2[lungimecoada2].l=curent.l-1;
			q2[lungimecoada2].c=curent.c-1;
			q2[lungimecoada2].dist=nouadist;
			x[curent.l-1][curent.c-1]=-1;
		}
		if (x[curent.l+1][curent.c]==0)

	{
			lungimecoada2++;
			q2[lungimecoada2].l=curent.l+1;
			q2[lungimecoada2].c=curent.c;
			q2[lungimecoada2].dist=nouadist;
			x[curent.l+1][curent.c]=-1;

	}
		if (x[curent.l-1][curent.c]==0)
		{
			lungimecoada2++;
			q2[lungimecoada2].l=curent.l-1;
	        q2[lungimecoada2].c=curent.c;
			q2[lungimecoada2].dist=nouadist;
			x[curent.l-1][curent.c]=-1;
		}
		indexcoada++;
	}
}



int main()
{

	f>>n>>m;

	lungimecoada1=0;
	lungimecoada2=0;
	for (i=0;i<=n;i++)
	{
		f.getline(s,101);
		for (j=0;j<strlen(s);j++)
			{
				if (s[j]=='R') {
								a[i][j+1]=2;

	lungimecoada1++;
								q1[lungimecoada1].l=i;
								q1[lungimecoada1].c=j+1;
								q1[lungimecoada1].dist=1;
				}
				if (s[j]=='J') {
								a[i][j+1]=3;
								lungimecoada2++;
								q2[lungimecoada2].l=i;
								q2[lungimecoada2].c=j+1;
								q2[lungimecoada2].dist=1;
				}
				if (s[j]=='X') {
								a[i][j+1]=1;
				}
				if (s[j]==' ') {
								a[i][j+1]=0;
				}
				x[i][j]=a[i][j];
		}
	}
	for (i=0;i<=n+1;i++) {
                           a[i][0]=-1;
                           a[i][m+1]=-1;
                        x[i][0]=-1;
                           x[i][m+1]=-1;
                        }
	for (i=0;i<=m+1;i++) {
                           a[0][i]=-1;
                           a[n+1][i]=-1;
                           x[0][i]=-1;
                           x[n+1][i]=-1;
                        }
	algoritmleeromeo();
	algoritmleejulieta();
	minim=10000;
        for (i=1;i<=lungimecoada1;i++)
		   for (j=1;j<=lungimecoada2;j++) if ((q1[i].l==q2[j].l)&&(q1[i].c==q2[j].c)&&(q1[i].dist==q2[j].dist))
		   {
                if (q1[i].dist<minim) {
                                    minim=q1[i].dist;
                                    minl=q1[i].l;
                                    minc=q1[i].c;
                                }
            }

  //  g<<lungimecoada1<<" "<<lungimecoada2<<endl;
    g<<minim<<" "<<minl<<" "<<minc;
    f.close();
    g.close();
    return 0;
}