Cod sursa(job #443099)

Utilizator siminescuPaval Cristi Onisim siminescu Data 16 aprilie 2010 00:42:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include<fstream>
using namespace std;
int a[101][101],b[101][101],n,m,x1,x2,p1,p2,in[100000],sf[100000];
void citire()
{
	ifstream f("rj.in");
	f>>n>>m;
	int i,j;
	f.get();
	char x;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f.get(x);
			if(x==' ')
				a[i][j]=b[i][j]=32000;
			if(x=='X')
				a[i][j]=b[i][j]=-1;
			if(x=='R')
			{
				x1=i;
				p1=j;
			}
			if(x=='J')
			{
				x2=i;
				p2=j;
			}
		}
		f.get();
	}
	f.close();
}
int main()
{
	citire();
	int i,j,pozi,pozj,min=32000,pin=0,psf=0;
	in[0]=x1;sf[0]=p1;
	while(pin<=psf)
	{
		if(b[in[pin]][sf[pin]-1]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]][sf[pin]-1]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin];sf[psf]=sf[pin]-1;
		}
		if(b[in[pin]][sf[pin]+1]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]][sf[pin]+1]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin];sf[psf]=sf[pin]+1;
		}
		if(b[in[pin]-1][sf[pin]]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]-1][sf[pin]]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]-1;sf[psf]=sf[pin];
		}
		if(b[in[pin]+1][sf[pin]]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]+1][sf[pin]]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]+1;sf[psf]=sf[pin];
		}
		if(b[in[pin]-1][sf[pin]-1]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]-1][sf[pin]-1]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]-1;sf[psf]=sf[pin]-1;
		}
		if(b[in[pin]+1][sf[pin]+1]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]+1][sf[pin]+1]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]+1;sf[psf]=sf[pin]+1;
		}
		if(b[in[pin]-1][sf[pin]+1]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]-1][sf[pin]+1]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]-1;sf[psf]=sf[pin]+1;
		}
		if(b[in[pin]+1][sf[pin]-1]>b[in[pin]][sf[pin]]+1)
		{
			b[in[pin]+1][sf[pin]-1]=b[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]+1;sf[psf]=sf[pin]-1;
		}
		pin++;
	}
	in[0]=x2;sf[0]=p2;
	pin=0;psf=0;
	while(pin<=psf)
	{
		if(a[in[pin]][sf[pin]-1]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]][sf[pin]-1]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin];sf[psf]=sf[pin]-1;
		}
		if(a[in[pin]][sf[pin]+1]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]][sf[pin]+1]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin];sf[psf]=sf[pin]+1;
		}
		if(a[in[pin]-1][sf[pin]]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]-1][sf[pin]]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]-1;sf[psf]=sf[pin];
		}
		if(a[in[pin]+1][sf[pin]]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]+1][sf[pin]]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]+1;sf[psf]=sf[pin];
		}
		if(a[in[pin]-1][sf[pin]-1]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]-1][sf[pin]-1]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]-1;sf[psf]=sf[pin]-1;
		}
		if(a[in[pin]+1][sf[pin]+1]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]+1][sf[pin]+1]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]+1;sf[psf]=sf[pin]+1;
		}
		if(a[in[pin]-1][sf[pin]+1]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]-1][sf[pin]+1]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]-1;sf[psf]=sf[pin]+1;
		}
		if(a[in[pin]+1][sf[pin]-1]>a[in[pin]][sf[pin]]+1)
		{
			a[in[pin]+1][sf[pin]-1]=a[in[pin]][sf[pin]]+1;
			psf++;
			in[psf]=in[pin]+1;sf[psf]=sf[pin]-1;
		}
		pin++;
	}
	ofstream g("rj.out");
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]==b[i][j]&&a[i][j]>0&&a[i][j]<min)
			{
				min=a[i][j];
				pozi=i;
				pozj=j;
			}
	g<<min+1<<" "<<pozi<<" "<<pozj;
}