Cod sursa(job #135755)

Utilizator damaDamaschin Mihai dama Data 14 februarie 2008 14:06:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
#include <string.h>

const int inf = 20000;

const int x[8] = {1, 1, 0, -1, -1, -1, 0, 1}, y[8] = {-1, 0, 1, -1, 0 , 1, -1, 1};

char mat[105][105];
int a[101][101], b[101][101], n, m, xj, yj, xr, yr, *q, solx, soly, sol = 20000;

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

	int i, j, alfa, beta, first, last, d;

	scanf("%d %d ", &n, &m);
	q = new int[n * m + 1];

	for(i = 0; i < n; ++i)
	{
		fgets(mat[i], 105, stdin);
	}

	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < m; ++j)
		{
			if(mat[i][j] == 'R')
			{
				xr = i;
				yr = j;
				b[i][j] = inf;
			}
			else if(mat[i][j] == 'J')
			{
				xj = i;
				yj = j;
				a[i][j] = inf;
			}
			else if(mat[i][j] == 'X')
			{
				a[i][j] = b[i][j] = -1;
			}
			else
			{
				a[i][j] = b[i][j] = inf;
			}
		}
	}

	first = last = 1;
	q[first] = 100 * xr + yr;

	while(first <= last)
	{
		alfa = q[first] / 100;
		beta = q[first] % 100;
		for(d = 0; d < 8; ++d)
		{
			if(alfa + x[d] >= 0 && alfa + x[d] < n && beta + y[d] >= 0 && beta + y[d] < m && a[alfa + x[d]][beta + y[d]] == inf)
			{
				a[alfa + x[d]][beta + y[d]] = a[alfa][beta] + 1;
				q[++last] = 100 * (alfa + x[d]) + beta + y[d];
			}
		}
		++first;
	}

	first = last = 1;
	q[first] = 100 * xj + yj;

	while(first <= last)
	{
		alfa = q[first] / 100;
		beta = q[first] % 100;
		for(d = 0; d < 8; ++d)
		{
			if(alfa + x[d] >= 0 && alfa + x[d] < n && beta + y[d] >= 0 && beta + y[d] < m && b[alfa + x[d]][beta + y[d]] == inf)
			{
				b[alfa + x[d]][beta + y[d]] = b[alfa][beta] + 1;
				q[++last] = 100 * (alfa + x[d]) + beta + y[d];
			}
		}
		++first;
	}
/*
	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < m; ++j)
		{
			printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < m; ++j)
		{
			printf("%d ", b[i][j]);
		}
		printf("\n");
	}

*/
	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < m; ++j)
		{
			if(a[i][j] == b[i][j] && a[i][j] != -1 && a[i][j] < sol)
			{
				sol = a[i][j];
				solx = i;
				soly = j;

			}
		}
	}

	printf("%d %d %d\n", sol + 1, solx + 1, soly + 1);

	return 0;
}