Cod sursa(job #553168)

Utilizator eukristianCristian L. eukristian Data 13 martie 2011 18:14:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <queue>
using namespace std;
enum Color {white, black, gray};
const int INF = 9999, dt[3] = {-1, 0, 1};

int M,N,rom,jul;

char mat[151][151];
inline int to_single_coord(int x, int y)
{
	int temp = (x << 8) + y;
	return temp;
}

inline void to_double_coord(int dc, int *x, int *y)
{
	*x = dc >> 8;
	*y = dc & 255;
}

inline bool eValid(int x, int y)
{
	return (x >= 1 && x <= N) && (y >= 1 && y <= M);
}

void read();
void bfs();

int main()
{
	read();
	bfs();
	return 0;
}


void read()
{
	freopen("rj.in", "r", stdin);
	scanf("%d %d\n", &N, &M);
	
	for (int i = 1 ; i <= N ; ++i)
		gets(mat[i] + 1);
}

void bfs()
{
	FILE *f = fopen("rj.out","w");
	int dist[2][151][151];
	Color color[151][151];
	 
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 1; j <= M ; ++j)
		{
			color[i][j] = white;
			dist[0][i][j]  = dist[1][i][j] = INF;
			
			if (mat[i][j] == 'R')
				rom = to_single_coord(i,j);
			else if (mat[i][j] == 'J')
				jul = to_single_coord(i,j);
		}	
	int xc, yc;
	to_double_coord(rom, &xc, &yc);
	dist[0][xc][yc]  = 0;
	color[xc][yc] = gray;
	
			
	queue<int> Q;
	Q.push(rom);
	
	while (!Q.empty())
	{
		int current_single_coord = Q.front();
		Q.pop();
		to_double_coord(current_single_coord, &xc, &yc);
		
		for (int i = 0 ; i < 3; ++i)
		{
			for (int j = 0 ; j < 3; ++j)
			{
				if (i == 1 && j == 1)
					continue;
				
				int cxc = xc + dt[i], cyc = yc + dt[j];
				if (eValid(cxc, cyc))
				{
					if (color[cxc][cyc] == white && mat[cxc][cyc] != 'X')
					{
						color[cxc][cyc] = gray;
						dist[0][cxc][cyc]  = dist[0][xc][yc] + 1;
						Q.push(to_single_coord(cxc, cyc));
					}

				}
			}
		}
		
		color[xc][yc] = black;
	}
	
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 1; j <= M ; ++j)
			color[i][j] = white;
			
	to_double_coord(jul, &xc, &yc);
	dist[1][xc][yc]  = 0;
	color[xc][yc] = gray;
			
	Q.push(jul);
	
	while (!Q.empty())
	{
		int current_single_coord = Q.front();
		Q.pop();
		to_double_coord(current_single_coord, &xc, &yc);
		
		
		for (int i = 0 ; i < 3; ++i)
		{
			for (int j = 0 ; j < 3; ++j)
			{
				if (i == 1 && j == 1)
					continue;
				
				int cxc = xc + dt[i], cyc = yc + dt[j];
				if (eValid(cxc, cyc))
				{
					if (color[cxc][cyc] == white && mat[cxc][cyc] != 'X')
					{
						color[cxc][cyc] = gray;
						dist[1][cxc][cyc]  = dist[1][xc][yc] + 1;
						Q.push(to_single_coord(cxc, cyc));
					}

				}
			}
		}
		
		color[xc][yc] = black;
	}
	
	int mini = 1, minj = 1, mine = INF;
	
	for (int i = 1 ; i <= N ; ++i)
	{
		for (int j = 1; j <= M ; ++j)
		{
			if (dist[0][i][j] == dist[1][i][j] && dist[0][i][j] < mine)
			{
				mine = dist[0][i][j];mini = i;minj = j;
			}
		}
	}
	
	fprintf(f,"%d %d %d\n",mine + 1,mini,minj);
	fclose(f);
}