Cod sursa(job #1511665)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 26 octombrie 2015 23:50:15
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>

struct pozitie{int lin, col;} coada[102 * 102];

int ar[102][102], aj[102][102];

int linie[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int coloana[8]={0, 1, 1, 1, 0, -1, -1, -1};

int main ()
{
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);

	int n, m, i, j;

	scanf("%d%d", &n, &m);

	for(i=0; i<=n+1; i++)
		ar[i][0]=ar[i][m+1]=aj[i][0]=aj[i][m+1]=-1;

	for(j=0; j<=m+1; j++)
		ar[0][j]=ar[n+1][j]=aj[0][j]=aj[n+1][j]=-1;

	char car;
	int j1, j2, r1, r2;

	for(i=1; i<=n; i++)
	{
		scanf("%c", &car);

		for(j=1; j<=m; j++)
		{
			scanf("%c", &car);

			switch(car)
			{
				case 'X': ar[i][j]=aj[i][j]=-1; break;
				case 'J': j1=i; j2=j; break;
				case 'R': r1=i; r2=j; break;
			}
		}
	}

	int ic, sf, l, c;

	ic=sf=1;

	coada[1].lin=j1;
	coada[1].col=j2;
	aj[j1][j2]=1;

	while(ic<=sf)
	{
		for(i=0; i<8; i++)
		{
			l=linie[i]+coada[ic].lin;
			c=coloana[i]+coada[ic].col;

			if(aj[l][c]==0)
			{
				sf++;
				coada[sf].lin=l;
				coada[sf].col=c;
				aj[l][c]=aj[coada[ic].lin][coada[ic].col]+1;
			}
		}
		ic++;
	}


	ic=sf=1;

	coada[1].lin=r1;
	coada[1].col=r2;
	ar[r1][r2]=1;

	while(ic<=sf)
	{
		for(i=0; i<8; i++)
		{
			l=linie[i]+coada[ic].lin;
			c=coloana[i]+coada[ic].col;

			if(ar[l][c]==0)
			{
				sf++;
				coada[sf].lin=l;
				coada[sf].col=c;
				ar[l][c]=ar[coada[ic].lin][coada[ic].col]+1;
			}
		}
		ic++;
	}

	int min=1000000, minl=0, minc=0;

	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(ar[i][j]==aj[i][j] && ar[i][j]>0 && ar[i][j]<min)
			{
				min=ar[i][j];
				minl=i;
				minc=j;
			}

	printf("%d %d %d\n", min, minl, minc);

	return 0;
}