Cod sursa(job #232170)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 14 decembrie 2008 21:21:06
Problema Rj Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.18 kb
#include<stdio.h>
#define infile "rj.in"
#define outfile "rj.out"
#define nmax 105
#define mmax 105
struct coada //structura pentru coada
	{
	int i,j; //cele doua coordonate ale matricei
	};
const int ii[]={-1,-1,-1,0,0,1,1,1};
const int jj[]={-1,0,1,-1,1,-1,0,1};
char h[nmax][mmax]; //matricea cu harta orasului
int tr[nmax][mmax]; //harta de timpi pentru romeo
int tj[nmax][mmax]; //harta de timpi pentru julieta
int rx,ry,jx,jy; //pozitiile de start pentru romeo si julieta
int n,m; //numarul de linii respectiv coloane

void citire(char h[nmax][mmax], int *n, int *m)
	{
	int i,j;
	char v[mmax];
	scanf("%d %d\n",n,m); //citim numarul de linii respectiv coloane
	for(i=1;i<=*n;i++) //citim fiecare linie din fisier
		{
		fgets(v,mmax,stdin); //citim in vector
		for(j=1;j<=*m;j++)
			h[i][j]=v[j-1]; //o copiem din vector in matrice
		}
	}

//transformam harta in: 0-se poate trece; 1-nu se poate trece, si salvam pozitiile lui romeo si lui julieta
void creeaza_harta(char h[nmax][mmax], int n, int m, int *rx, int *ry, int *jx, int *jy)
	{
	int i,j;
	for(i=1;i<=n;i++) //fiecare linie
		for(j=1;j<=m;j++) //fiecare coloana
			if(h[i][j]==' ') h[i][j]=0; //prin spatii paote trece
			else if(h[i][j]=='X') h[i][j]=1; //prin obstacole nu poate trece
			else if(h[i][j]=='R') { h[i][j]=1; *rx=i; *ry=j; } //salvam pozitia lui Romeo
			else if(h[i][j]=='J') { h[i][j]=1; *jx=i; *jy=j; } //salvam pozitia Julietei
	}

//creeaza harta de timpi
void fai_harta_timp(char h[nmax][mmax], int t[nmax][mmax], int n, int m, int x, int y)
	{
	struct coada v[nmax*mmax]; //coada
	int p,q; //capetele cozii
	int i,j,k;
	p=q=1; v[p].i=x; v[p].j=y; //initializam coada
	while(p<=q) //cat timp avem elemente in coada
		{
		for(k=0;k<8;k++) //cele 8 pozitii de vecini
			{
			i=v[p].i+ii[k]; //linia vecinului
			j=v[p].j+jj[k]; //coloana vecinului
			if(i>0 && i<=n && j>0 && j<=m && !h[i][j] && (!t[i][j] || t[v[p].i][v[p].j]+1<t[i][j])) //daca se afla in interiorul hartii, si daca ajunge intr-un timp mai scurt
				{
				t[i][j]=t[v[p].i][v[p].j]+1; //salvam costul cu care se ajunge
				q++; //largim coada
				v[q].i=i; v[q].j=j; //salvam pozitia in coada
				}
			}
		p++;
		}
	}

int main()
{
int t=nmax*mmax,x,y; //pozitia de intalnire, si timpul
int i,j;
//deschidem
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(h,&n,&m); //citim dimensiunea hartii si harta
creeaza_harta(h,n,m,&rx,&ry,&jx,&jy); //modificam harta in 0 si 1, si aflam pozitiile celor doi
fai_harta_timp(h,tr,n,m,rx,ry); //facem matricea de timp pentru Romeo
fai_harta_timp(h,tj,n,m,jx,jy); //facem matricea de timpi pentru Julieta

//cautam punctul de intalnire cu timpul cel mai scurt
for(i=1;i<=n;i++) //fiecare linie
	for(j=1;j<=m;j++) //fiecare coloana din linie
		if(tr[i][j]==tj[i][j] && tr[i][j]>0 && tr[i][j]<t) //daca timpul facut de romeo si julieta pentru a ajunge in punctul ij este egal , si timpul este mai scurt decat cel mai scurt de pana acum
			{
			x=i; y=j; //salvam pozitia
			t=tr[i][j]; //salvam timpul minim
			}

printf("%d %d %d\n",t+1,x,y); //afisem timpul minim de itnalnire, si coordonatele locului

//inchidem
fclose(stdin);
fclose(stdout);
return 0;
}