Cod sursa(job #345135)

Utilizator prdianaProdan Diana prdiana Data 1 septembrie 2009 20:05:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <stdio.h>
#include <queue>
#include <string.h>

#define MAXN 128

using namespace std;

int dir[16] = {0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};

struct point
{
	int x,y;
	point(int vx,int vy)
	{
		x = vx;
		y = vy;
	}
	point()
	{
	}
};

char h[MAXN][MAXN];
int n,m,i,k;
int r[MAXN][MAXN],j[MAXN][MAXN];
bool viz[MAXN][MAXN];
int best = 99999999,maxx,maxy;
queue<point> q;

void bfs(int val[MAXN][MAXN],point &first)
{
	q.push(first);
	memset(viz,0,sizeof(viz));
	viz[first.y][first.x] = true;
	val[first.y][first.x] = true;
	int x,y;
	for (i=0;i<=n+1;i++)
	{
		viz[i][0] = true;
		viz[i][m+1] = true;
	}
	for (i=0;i<=m+1;i++)
	{
		viz[0][i] = true;
		viz[n+1][i] = true;
	}
	while (!q.empty())
	{
		x = q.front().x;
		y = q.front().y;
		for (i=0;i<=16;i+=2)
		{
			if (!viz[y+dir[i]][x+dir[i+1]] && h[y+dir[i]][x+dir[i+1]] != 'X')
			{
				q.push(point(x+dir[i+1],y+dir[i]));
				viz[y+dir[i]][x+dir[i+1]] = true;
				val[y+dir[i]][x+dir[i+1]] = val[y][x] + 1;
			}
		}
		q.pop();
	}

}
void solve()
{
	for (i=1;i<=n;i++)
	{
		for (k=1;k<=m;k++)
		{
			if (r[i][k] == j[i][k] && best>r[i][k] && viz[i][k])
			{
				best = r[i][k];
				maxx = k;
				maxy = i;
			}
		}
	}
}

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

	scanf("%d%d\n",&n,&m);
	char aux;
	point jf,rf;
	for (i=1;i<=n;i++)
	{
		for (k=1;k<=m;k++)
		{
			scanf("%c",&h[i][k]);
			if (h[i][k] == 'R')
			{
				rf.x = k;
				rf.y = i;
			}
			if (h[i][k] == 'J')
			{
				jf.x = k;
				jf.y = i;
			}
		}
		scanf("%c",&aux);
	}
	bfs(r,rf);
	for (i=0;i>-1;);
	bfs(j,jf);
	solve();
	printf("%d %d %d",best,maxy,maxx);

	return 0;
}