Cod sursa(job #566760)

Utilizator gabriel93Robu Gabriel gabriel93 Data 29 martie 2011 11:52:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include<fstream>
#include<string.h>
using namespace std;
fstream f1,f2;
char a[102][102],x[102];
struct pozitie
{
	int l,c;
	pozitie *adresa;
};
pozitie *startr1,*startr2,*startj1,*startj2,*start3;
void init()
{
	startr1=NULL;
	startr2=NULL;
	startj1=NULL;
	startj2=NULL;
	start3=NULL;
}
void adaugr1(int l1, int c1)
{
	pozitie *p;
	p=new pozitie;
	p->l=l1;
	p->c=c1;
	p->adresa=startr1;
	startr1=p;
}
void adaugr2(int l1, int c1)
{
	pozitie *p;
	p=new pozitie;
	p->l=l1;
	p->c=c1;
	p->adresa=startr2;
	startr2=p;
}
void adaugj1(int l1, int c1)
{
	pozitie *p;
	p=new pozitie;
	p->l=l1;
	p->c=c1;
	p->adresa=startj1;
	startj1=p;
}
void adaugj2(int l1, int c1)
{
	pozitie *p;
	p=new pozitie;
	p->l=l1;
	p->c=c1;
	p->adresa=startj2;
	startj2=p;
}
void adaug3(int l1, int c1)
{
	pozitie *p;
	p=new pozitie;
	p->l=l1;
	p->c=c1;
	p->adresa=start3;
	start3=p;
}
void sterg1(pozitie *adr)
{
	pozitie *p;
	if(adr==NULL)
	{
		p=startr1;
		startr1=startr1->adresa;
		delete p;
	}
	else
	{
		p=adr->adresa;
		adr->adresa=p->adresa;
		delete p;
	}
}
void sterg2(pozitie *adr)
{
	pozitie *p;
	if(adr==NULL)
	{
		p=startj1;
		startj1=startj1->adresa;
		delete p;
	}
	else
	{
		p=adr->adresa;
		adr->adresa=p->adresa;
		delete p;
	}
}
int main()
{
int x1,x2,y1,y2,k,q,xx1,yy1,b[101][101],ok,xx2,yy2;
int xx3,yy3,lmin,cmin,j,i,m,n;
int dl[8]={-1,-1,0,+1,+1,+1,0,-1};
int dc[8]={0,+1,+1,+1,0,-1,-1,-1};
f1.open("rj.in",ios::in);
f2.open("rj.out",ios::out);
f1>>n>>m;
f1.get();
for(i=1;i<=n;i++)
{
	f1.get(x,m+1,'\n');
	f1.get();
	strcpy(a[i]," ");
	strcat(a[i],x);
}
x1=x2=y1=y2=xx1=xx2=yy1=yy2=xx3=yy3=0;
for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		if(a[i][j]=='R')
		{
			x1=i;
			y1=j;
			b[i][j]=1;
		}
		if(a[i][j]=='J')
		{
			x2=i;
			y2=j;
			b[i][j]=0;
		}
		if(a[i][j]==' ')
			b[i][j]=0;
		if(a[i][j]=='X')
			b[i][j]=-1;
	}
k=1;
startr1=NULL;
startj1=NULL;
adaugr1(x1,y1);
adaugj1(x2,y2);
q=0;
pozitie *p;
while(!q)
{
	startr2=NULL;
	while(startr1)
	{
		for(j=0;j<=7;j++)
		{
			xx1=startr1->l+dl[j];
			yy1=startr1->c+dc[j];
			if(xx1>0&&xx1<=n&&yy1>0&&yy1<=m)
				if(b[xx1][yy1]==0)
				{
					b[xx1][yy1]=2;
					adaugr2(xx1,yy1);
				}
		}
		sterg1(NULL);
	}
	startj2=NULL;
	while(startj1)
	{
		for(j=0;j<=7;j++)
		{
			xx2=startj1->l+dl[j];
			yy2=startj1->c+dc[j];
			if(xx2>0&&xx2<=n&&yy2>0&&yy2<=m)
				if(b[xx2][yy2]==0)
				{
					b[xx2][yy2]=3;
					adaugj2(xx2,yy2);
				}
				else if (b[xx2][yy2]==2)
				{
					q++;
					adaug3(xx2,yy2);
					b[xx2][yy2]=4;
				}
				
		}
		sterg2(NULL);
	}
	k++;
	startr1=startr2;
	startj1=startj2;
	for(p=startr2;p!=NULL;p=p->adresa)
		b[p->l][p->c]=1;
}
ok=k;
lmin=n+1;
cmin=m+1;
for (p=start3;p!=NULL;p=p->adresa)
	if ((p->l<lmin) || (p->l==lmin&&p->c<cmin))
	{
		lmin=p->l;
		cmin=p->c;
	}
f2<<ok<<" "<<lmin<<" "<<cmin;
f1.close();
f2.close();
return 0;
}