Cod sursa(job #454646)

Utilizator ChallengeMurtaza Alexandru Challenge Data 12 mai 2010 10:05:46
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <stdio.h>
#include <vector>

using namespace std;

const char InFile[]="rj.in";
const char OutFile[]="rj.out";
const int MaxN=205;

FILE *f;
int r[MaxN][MaxN];
int j[MaxN][MaxN];
int n,m,rx,ry,jx,jy,minx,miny,mins=1<<30;
char c;

struct pos{int x,y;};

void lee_r()
{
	for(int i=0;i<=n+1;++i)
	{
		r[i][0]=-1;
		r[i][m+1]=-1;
	}
	for(int i=0;i<=m+1;++i)
	{
		r[0][i]=-1;
		r[n+1][i]=-1;
	}
	
	vector<pos> v1,v2;
	pos t;
	t.x=rx;
	t.y=ry;
	v1.push_back(t);
	int step=1;
	r[rx][ry]=step;
	while(v1.size())
	{
		++step;
		for(int i=0;i<(int)v1.size();++i)
		{
			if(r[v1[i].x+1][v1[i].y]==0)
			{
				r[v1[i].x+1][v1[i].y]=step;
				t.x=v1[i].x+1;
				t.y=v1[i].y;
				v2.push_back(t);
			}
			if(r[v1[i].x-1][v1[i].y]==0)
			{
				r[v1[i].x-1][v1[i].y]=step;
				t.x=v1[i].x-1;
				t.y=v1[i].y;
				v2.push_back(t);
			}
			if(r[v1[i].x][v1[i].y+1]==0)
			{
				r[v1[i].x][v1[i].y+1]=step;
				t.x=v1[i].x;
				t.y=v1[i].y+1;
				v2.push_back(t);
			}
			if(r[v1[i].x][v1[i].y-1]==0)
			{
				r[v1[i].x][v1[i].y-1]=step;
				t.x=v1[i].x;
				t.y=v1[i].y-1;
				v2.push_back(t);
			}
			
			if(r[v1[i].x+1][v1[i].y+1]==0)
			{
				r[v1[i].x+1][v1[i].y+1]=step;
				t.x=v1[i].x+1;
				t.y=v1[i].y+1;
				v2.push_back(t);
			}
			if(r[v1[i].x+1][v1[i].y-1]==0)
			{
				r[v1[i].x+1][v1[i].y-1]=step;
				t.x=v1[i].x+1;
				t.y=v1[i].y-1;
				v2.push_back(t);
			}
			if(r[v1[i].x-1][v1[i].y+1]==0)
			{
				r[v1[i].x-1][v1[i].y+1]=step;
				t.x=v1[i].x-1;
				t.y=v1[i].y+1;
				v2.push_back(t);
			}
			if(r[v1[i].x-1][v1[i].y-1]==0)
			{
				r[v1[i].x-1][v1[i].y-1]=step;
				t.x=v1[i].x-1;
				t.y=v1[i].y-1;
				v2.push_back(t);
			}
		}
		v1=v2;
		v2.resize(0);
	}
}

void lee_j()
{
	for(int i=0;i<=n+1;++i)
	{
		j[i][0]=-1;
		j[i][m+1]=-1;
	}
	for(int i=0;i<=m+1;++i)
	{
		j[0][i]=-1;
		j[n+1][i]=-1;
	}
	
	vector<pos> v1,v2;
	pos t;
	t.x=jx;
	t.y=jy;
	v1.push_back(t);
	int step=1;
	j[jx][jy]=step;
	while(v1.size())
	{
		++step;
		for(int i=0;i<(int)v1.size();++i)
		{
			if(j[v1[i].x+1][v1[i].y]==0)
			{
				j[v1[i].x+1][v1[i].y]=step;
				t.x=v1[i].x+1;
				t.y=v1[i].y;
				v2.push_back(t);
			}
			if(j[v1[i].x-1][v1[i].y]==0)
			{
				j[v1[i].x-1][v1[i].y]=step;
				t.x=v1[i].x-1;
				t.y=v1[i].y;
				v2.push_back(t);
			}
			if(j[v1[i].x][v1[i].y+1]==0)
			{
				j[v1[i].x][v1[i].y+1]=step;
				t.x=v1[i].x;
				t.y=v1[i].y+1;
				v2.push_back(t);
			}
			if(j[v1[i].x][v1[i].y-1]==0)
			{
				j[v1[i].x][v1[i].y-1]=step;
				t.x=v1[i].x;
				t.y=v1[i].y-1;
				v2.push_back(t);
			}
			
			if(j[v1[i].x+1][v1[i].y+1]==0)
			{
				j[v1[i].x+1][v1[i].y+1]=step;
				t.x=v1[i].x+1;
				t.y=v1[i].y+1;
				v2.push_back(t);
			}
			if(j[v1[i].x+1][v1[i].y-1]==0)
			{
				j[v1[i].x+1][v1[i].y-1]=step;
				t.x=v1[i].x+1;
				t.y=v1[i].y-1;
				v2.push_back(t);
			}
			if(j[v1[i].x-1][v1[i].y+1]==0)
			{
				j[v1[i].x-1][v1[i].y+1]=step;
				t.x=v1[i].x-1;
				t.y=v1[i].y+1;
				v2.push_back(t);
			}
			if(j[v1[i].x-1][v1[i].y-1]==0)
			{
				j[v1[i].x-1][v1[i].y-1]=step;
				t.x=v1[i].x-1;
				t.y=v1[i].y-1;
				v2.push_back(t);
			}
		}
		v1=v2;
		v2.resize(0);
	}
}

int main()
{
	f=fopen(InFile,"r");
	fscanf(f,"%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		fscanf(f,"%c",&c);
		for(int k=1;k<=m;++k)
		{
			fscanf(f,"%c",&c);
			if(c=='X')
			{
				r[i][k]=-1;
				j[i][k]=-1;
			}
			else if(c=='R')
			{
				rx=i;
				ry=k;
			}
			else if(c=='J')
			{
				jx=i;
				jy=k;
			}
		}
	}
	fclose(f);
	
	lee_r();
	lee_j();
	
	for(int i=1;i<=n;++i)
	{
		for(int k=1;k<=m;++k)
		{
			if(r[i][k]==j[i][k] && r[i][k]>0 && r[i][k]<mins)
			{
				mins=r[i][k];
				minx=i;
				miny=k;
			}
		}
	}
	
	f=fopen(OutFile,"w");
	fprintf(f,"%d %d %d",mins,minx,miny);
	fclose(f);
	return 0;
}