Cod sursa(job #136305)

Utilizator peanutzAndrei Homorodean peanutz Data 15 februarie 2008 13:47:55
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <string.h>

#define NMAX 103

short map[NMAX][NMAX];
int tj[NMAX][NMAX], tr[NMAX][NMAX];
int n, m;


void read()
{
	char s[NMAX];
	int i, j;
	scanf("%d %d\n", &n, &m);


	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			tj[i][j] = tr[i][j] = 32000;

	for(i = 1; i <= n; ++i)
	{
		fgets(s+1, NMAX, stdin);
		for(j = 1; j <= m; ++j)
			if(s[j] == ' ')
				map[i][j] = 1;
			else if(s[j] == 'R')
				map[i][j] = 2, tr[i][j] = 0;
			else if(s[j] == 'J')
				map[i][j] = 3, tj[i][j] = 0;
			else
				map[i][j] = 0;
	}

}

inline int MIN(int a, int b) { return (a < b) ? (a) : (b); }


void bf1()
{
	int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
	int i, j, k;
	short ok = 1;
	while(ok)
	{
	ok = 0;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			if(map[i][j] != 0)
				for(k = 0; k < 4; ++k)
					if(map[ i-dx[k] ][ j-dy[k] ] != 0)
						if(tj[ i-dx[k] ][ j-dy[k] ] > tj[i][j]+1)
							tj[ i-dx[k] ][ j-dy[k] ] = tj[i][j]+1, ok = 1;
	}
}


void bf2()
{
	int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
	int i, j, k;
	short ok = 1;
	while(ok)
	{
	ok = 0;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			if(map[i][j] != 0)
				for(k = 0; k < 4; ++k)
					if(map[ i-dx[k] ][ j-dy[k] ] != 0)
						if(tr[ i-dx[k] ][ j-dy[k] ] > tr[i][j]+1)
							tr[ i-dx[k] ][ j-dy[k] ] = tr[i][j]+1, ok = 1;
	}
}

void find()
{
	int t = 0;
	int i, j;
	while(1)
	{
		++t;
		for(i = 1; i <= n; ++i)
			for(j = 1; j <= m; ++j)
				if(tj[i][j] == t && tj[i][j] == tr[i][j])
				{
					printf("%d %d %d\n", t, i, j);
					return ;
				}
	}
}





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

	read();

	bf1();

	bf2();

	find();


	return 0;
}