Cod sursa(job #577901)

Utilizator balakraz94abcd efgh balakraz94 Data 10 aprilie 2011 19:08:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<fstream>
#define L 102
using namespace std;

void initializare();
void citeste();
void rezolva();
void afiseaza();
void lee(int a[L][L], int, int);


int m,n;//numarul de linii si coloane
int ro[L][L],ju[L][L];//matricile lui romeo si julieta 
int xri,yri,xji,yji;//pozitiile initiale ale lui romeo si julieta
int sol, iaux, jaux;//solutia si pozitia ei

int dx[]={0,1,-1,0,0,-1,1,1,-1};//directiile pe linie
int dy[]={0,0,0,1,-1,-1,1,-1,1};//directiile pe coloana

struct coada {int x,y;};
coada c[L*L];





void initializare()
{
	for(int i=0;i<L;i++) 
		for(int j=0;j<L;j++) 
			ro[i][j]=ju[i][j]=-2;//umplu matricile cu -2 (se poate trece)

	for(int i=0;i<=m+1;i++) ro[i][0]=ro[i][n+1]=ju[i][0]=ju[i][n+1]=-1;//bordare verticala
	
	for(int i=0;i<=n+1;i++) ro[0][i]=ro[m+1][i]=ju[0][i]=ju[m+1][i]=-1;//bordare orizontala
}




void citeste()
{
	char s[L+2];
	int i,j;
	
	ifstream fin ("rj.in");
	
	fin>>m>>n;//citesc nr de linii si coloane
	fin.get();//citesc spatiul ramas
	
	initializare();//initializez matricile
	
	for(i=1;i<=m;i++) 
	{
		fin.getline(s,102);//citesc linia i in sirul de caractere s
		for( j=0;j<n;j++) //parcurg sirul s de la 0
		{ 
			if(s[j]=='X') ro[i][j+1]=ju[i][j+1]=-1;//onstacol
			  else if(s[j]=='R') xri=i, yri=j+1;//pozitia lui romeo
					 else if (s[j]=='J') xji=i, yji=j+1;//pozitia julietei
		}	
	}
	fin.close();
}



void rezolva()
{
	lee(ro,xri,yri);//alg lui lee pt romeo
	lee(ju,xji,yji);//alg lui lee pt julieta

	sol=L*L+1;//punctul de intalnire comun minim
	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n+1;j++) 
			if(ro[i][j]==ju[i][j] && ro[i][j]>1)
				if(ro[i][j]<sol) {sol=ro[i][j];iaux=i;jaux=j;}//daca am gasit un punct de intalnire minim il salvez
}



void lee(int a[L][L],int xi,int yi)
{
	int xc,yc,mc,x2,y2,i;
    int p,u;
	
	p=u=1;//coada are initial o singura pozitie - cea de start
	c[p].x=xi;// pun pozitia pe axa x in coada
	c[p].y=yi;//pun pozitia pe axa y in coada
	a[xi][yi]=1;//pozitia de plecare
	
	while(p<=u)//cat timp nu am ajuns la sfarsitul cozii
	{
		xc=c[p].x;//x curent
		yc=c[p].y;//y curent
		mc=a[xc][yc];//marcajul(pasul) curent
		
		for(i=1;i<=8;i++) //iau cele 8 directii
		{
			x2=xc+dx[i];
			y2=yc+dy[i];
			
			if(a[x2][y2]==-2)//daca se poate trece(e liber)
			{
				u++;//maresc coada
				c[u].x=x2;//adaug noua pozitie in coada
				c[u].y=y2;
				a[x2][y2]=mc+1;//am facut numarul de pasi anteriori + 1
			}
		}
		p++;//incrementez p (trec la urmatorul element din coada)
	}
}


void afiseaza()
{
	ofstream fout("rj.out");
	
	fout<<sol<<" "<<iaux<<" "<<jaux;//afisez solutia si pozitia unde am gasit-o
	
	fout.close();
}

int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}