Cod sursa(job #867144)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 29 ianuarie 2013 10:53:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb

#include <cstdio>

const int MAX_SIZE(102);
const int MAX_VALUE(1 << 30);

int n, m, t(MAX_VALUE);

int matrix [MAX_SIZE] [MAX_SIZE];

struct coord
{
	int i;
	int j;
} queue [MAX_SIZE * MAX_SIZE], point;

inline void read (void)
{
	std::freopen("rj.in","r",stdin);
	std::scanf("%d %d\n",&n,&m);
	char s [MAX_SIZE + 1];
	int i, j;
	for (i = 1 ; i <= n ; ++i)
	{
		std::fgets(s + 1,MAX_SIZE,stdin);
		for (j = 1 ; j <= m ; ++j)
			if (s[j] == 'X')
				matrix[i][j] = MAX_VALUE;
			else if (s[j] == 'R')
			{
				matrix[i][j] = -1;
				queue[0].i = i;
				queue[0].j = j;
			}
			else if (s[j] == 'J')
			{
				matrix[i][j] = 1;
				queue[1].i = i;
				queue[1].j = j;
			}
	}
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("rj.out","w",stdout);
	std::printf("%d %d %d\n",t,point.i,point.j);
	std::fclose(stdout);
}

inline void initialize (void)
{
	int index, auxn(n + 1), auxm(m + 1);
	for (index = 0 ; index <= auxn ; ++index)
		matrix[index][0] = matrix[index][auxm] = MAX_VALUE;
	for (index = 0 ; index <= auxm ; ++index)
		matrix[0][index] = matrix[auxn][index] = MAX_VALUE;
}

inline int abs (const int x)
{
	return x < 0 ? -x : x;
}

inline bool sign (const int x)
{
	return x < 0;
}

inline int increment (const int x)
{
	return x + (sign(x) ? -1 : 1);
}

inline void dynamic (void)
{
	static const int WAYS(8);
	static const int X [ ] = {-1,-1, 0, 1, 1, 1, 0,-1};
	static const int Y [ ] = { 0, 1, 1, 1, 0,-1,-1,-1};
	int i, j, x, y, direction;
	struct coord *push(queue + 2), *pop(queue);
	while (pop < push)
	{
		i = pop->i;
		j = pop->j;
		++pop;
		for (direction = 0 ; direction < WAYS ; ++direction)
		{
			x = i + X[direction];
			y = j + Y[direction];
			if (matrix[x][y] == MAX_VALUE)
				continue;
			if (!matrix[x][y])
			{
				matrix[x][y] = increment(matrix[i][j]);
				push->i = x;
				push->j = y;
				++push;
			}
			else if (matrix[i][j] * matrix[x][y] < 0)
			{
				if (abs(increment(matrix[i][j])) == abs(matrix[x][y]))
				{
					if (abs(matrix[x][y]) < t)
					{
						t = abs(matrix[x][y]);
						point.i = x;
						point.j = y;
					}
					else if (abs(matrix[x][y]) == t)
					{
						if (x < point.i)
						{
							point.i = x;
							point.j = y;
						}
						else if (x == point.i && y < point.j)
						{
							point.i = x;
							point.j = y;
						}
					}
				}
			}
		}
	}
}

int main (void)
{
	read();
	initialize();
	dynamic();
	print();
	return 0;
}