Cod sursa(job #866892)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 28 ianuarie 2013 21:10:26
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb

#include <cstdio>
#include <iostream>

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];
	int i, j;
	for (i = 1 ; i <= n ; ++i)
	{
		std::gets(s + 1);
		std::scanf("\n");
		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 (int x)
{
	return x > 0 ? x : -x;
}

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

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] = matrix[i][j] + (sign(matrix[i][j]) ? -1 : 1);
				push->i = x;
				push->j = y;
				++push;
			}
			else if (matrix[i][j] * matrix[x][y] < 0)
				if (abs(matrix[i][j] + (sign(matrix[i][j]) ? -1 : 1)) == 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 (y < point.j)
						{
							point.i = x;
							point.j = y;
						}
				}
		}
	}
}

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