Cod sursa(job #553118)

Utilizator eukristianCristian L. eukristian Data 13 martie 2011 17:09:00
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 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[101][101];
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)
	{
		for (int j = 1 ; j <= M ; ++j)
		{
			scanf("%c", &mat[i][j]);
			if (mat[i][j] == 'R')
				rom = to_single_coord(i,j);
			else if (mat[i][j] == 'J')
				jul = to_single_coord(i,j);
		}
		scanf("\n");
	}
}

void bfs()
{
	freopen("rj.out","w",stdout);
	int dist[101][101];
	Color color[101][101];
	 
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 1; j <= M ; ++j)
		{
			color[i][j] = white;
			dist[i][j]  = INF;
		}	
		
	int xc, yc;
	to_double_coord(rom, &xc, &yc);
	dist[xc][yc]  = 0;
	color[xc][yc] = gray;
	
	to_double_coord(jul, &xc, &yc);
	dist[xc][yc]  = 0;
	color[xc][yc] = gray;
			
	queue<int> Q;
	Q.push(rom);Q.push(jul);
	
	while (!Q.empty())
	{
		int current_single_coord = Q.front();
		Q.pop();
		to_double_coord(current_single_coord, &xc, &yc);
		
		if (xc < N - 1)
		{
			if (color[xc + 1][yc] == white && mat[xc + 1][yc] == ' ')
			{
				color[xc + 1][yc] = gray;
				dist[xc + 1][yc]  = dist[xc][yc] + 1;
				Q.push(to_single_coord(xc + 1, 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] == ' ')
					{
						color[cxc][cyc] = gray;
						dist[cxc][cyc]  = dist[xc][yc] + 1;
						Q.push(to_single_coord(cxc, cyc));
					}
					else if (color[cxc][cyc] != white && dist[cxc][cyc] == dist[xc][yc] + 1)
					{
						printf("%d %d %d\n",cxc,cyc,dist[cxc][cyc] + 1);
					}
				}
			}
		}
		
		color[xc][yc] = black;
	}

}