Cod sursa(job #136389)

Utilizator peanutzAndrei Homorodean peanutz Data 15 februarie 2008 15:20:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <stdio.h>
#include <string.h>

#define NMAX 105

short map[NMAX][NMAX];
int tj[NMAX][NMAX], tr[NMAX][NMAX];
int n, m;
int jx, jy, rx, ry;


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] = 1, rx = i, ry = j;
			else if(s[j] == 'J')
				map[i][j] = 3, tj[i][j] = 1, jx = i, jy = j;
			else
				map[i][j] = 0;
	}
	///printf("%d\n", m);

}

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

void bf1()
{
	int m;
	int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
	int qx[NMAX*NMAX], qy[NMAX*NMAX];
	int inc, sf;
	int x, y, k, i, j;

	inc = sf = 1;
	qx[inc] = jx;
	qy[inc] = jy;


	while(inc <= sf)
	{
		i = qx[inc];
		j = qy[inc++];

		for(k = 0; k < 8; ++k)
			if(map[ i+dx[k] ][ j+dy[k] ])
				if(tj[ i+dx[k] ][ j+dy[k] ] > tj[i][j]+1)
				{
					tj[ i+dx[k] ][ j+dy[k] ] = tj[i][j]+1;
					qx[++sf] = i+dx[k];
					qy[sf] = j+dy[k];
				}
	}
}



void bf2()
{
	int m;
	int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
	int qx[NMAX*NMAX], qy[NMAX*NMAX];
	int inc, sf;
	int x, y, k, i, j;

	inc = sf = 1;
	qx[inc] = rx;
	qy[inc] = ry;


	while(inc <= sf)
	{
		i = qx[inc];
		j = qy[inc++];

		for(k = 0; k < 8; ++k)
			if(map[ i+dx[k] ][ j+dy[k] ])
				if(tr[ i+dx[k] ][ j+dy[k] ] > tr[i][j]+1)
				{
					tr[ i+dx[k] ][ j+dy[k] ] = tr[i][j]+1;
					qx[++sf] = i+dx[k];
					qy[sf] = j+dy[k];
				}
	}
}

int mere(int x)
{
	//return 1;
	int i, j;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			if(x >= tr[i][j] && tr[i][j] == tj[i][j])
				return 1;
	return 0;
}


void find()
{
	int i, j;
	int st = 1, dr = 32000;
	int mid, keep;
	while(st <= dr)
	{
		mid = (st + dr) /2;

		if(mere(mid))
		{
			keep = mid;
			dr = mid-1;
		}
		else
			st = mid+1;

	}
	printf("%d ", keep);
	for(i = 1; i <= n;++i)
		for(j = 1; j <= m;++j)
			if(keep == tr[i][j] && tr[i][j] == tj[i][j])
			{
				printf("%d %d\n", i, j);
				return ;
			}
}


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

	read();

	bf1();
	bf2();


	//printf("%d\n", m);

	find();


	return 0;
}