Cod sursa(job #344537)

Utilizator Ionescu_MariaIonescu Maria-Dorina Ionescu_Maria Data 30 august 2009 15:15:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream.h>
#include<string.h>
#define nmax 105
int a[nmax][nmax],n,m,sw,tmin,xmin,ymin,rx,ry,jx,jy,xr[10002],yr[10002],xj[10002],yj[10002];
int dl[8]={0,0,1,-1,1,1,-1,-1};
int dc[8]={1,-1,0,0,1,-1,1,-1};
void cit()
{
	ifstream fin("rj.in");
	char c;
	fin>>n>>m;
	fin.get();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			c=fin.get();
			if(c=='R')
			{
				rx=i; ry=j;
			}
			else
				if(c=='J')
				{
					jx=i; jy=j;
				}
				else
					if(c=='X')
						a[i][j]=-1;
		}
		fin.get();
	}
	fin.close();
}
void bordare()
{
	int i;
	for(i=0;i<=n+1;i++)
		a[i][0]=a[i][m+1]=-1;
	for(i=1;i<=m;i++)
		a[0][i]=a[n+1][i]=-1;
}
int verif(int ii,int jj)
{
	if(sw==0)
		return 1;
	if(ii<xmin)
		return 1;
	if(ii==xmin&&jj<ymin)
		return 1;
	return 0;
}
void lee()
{
	int u,i,j,ii,jj,k,k1,k2,k3,k4,t,dd;
	xr[1]=rx; yr[1]=ry; a[rx][ry]=1; xj[1]=jx; yj[1]=jy; a[jx][jy]=1;
	u=k1=k2=k3=k4=1;
	sw=0;
	while(sw==0)
	{
		u=k2;
		for(t=k1;t<=k2;t++)
		{
			i=xr[t]; j=yr[t]; dd=a[i][j]+1;
			for(k=0;k<8;k++)
			{
				ii=i+dl[k]; jj=j+dc[k];
				if(a[ii][jj]==0)
				{
					u++; xr[u]=ii; yr[u]=jj; a[ii][jj]=dd;
				}
			}
		}
		k1=k2+1;
		k2=u;
		u=k4;
		for(t=k3;t<=k4;t++)
		{
			i=xj[t]; j=yj[t]; dd=a[i][j]+1;
			for(k=0;k<8;k++)
			{
				ii=i+dl[k]; jj=j+dc[k];
				if(a[ii][jj]==0)
				{
					u++; xj[u]=ii; yj[u]=jj; a[ii][jj]=dd;
				}
				else
					if(a[ii][jj]==dd&&verif(ii,jj))
					{
						sw=1;
						tmin=dd;
						xmin=ii;
						ymin=jj;
					}
			}
		}
		k3=k4+1;
		k4=u;
	}
}
void afis()
{
	ofstream fout("rj.out");
	fout<<tmin<<" "<<xmin<<" "<<ymin<<'\n';
	fout.close();
}
int main()
{
	cit();
	bordare();
	lee();
	afis();
	return 0;
}