Cod sursa(job #258699)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 15 februarie 2009 10:49:44
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define FIN "rj.in"
#define FOUT "rj.out"
#define N 110
using namespace std;
const int dx[]={0,1,1,1,0,-1,-1,-1};
const int dy[]={-1,-1,0,1,1,1,0,-1};
queue < pair <int,int> > q;
pair <int,int> cr,cj,r[N][N];
int n,m,tmin = N * N,mi,mj;
void proba()
{
	int i,j;
	for (i = 1; i <= n; ++i)
	{
		for (j = 1; j <= m; ++j)
			printf("(%d,%d)\t",r[i][j].first,r[i][j].second);
		printf("\n");
	}
	printf("\n");
}
void read()
{
	int i,j;
	char c[N];
	freopen(FIN,"r",stdin);
	scanf("%d%d\n", &n, &m);
	mi = n; mj = m;
	for (i = 1; i <= n; ++i)
	{
		fgets(c,N,stdin);
		for ( j = 0; j < m; ++j)
		{
			if (c[j] == ' ')
				r[i][j+1].first = r[i][j+1].second = -1;
			if (c[j] == 'X')
				r[i][j+1].first = r[i][j+1].second = -2;
			if (c[j] == 'J')
			{
				cj = make_pair(i,j+1);
				r[i][j+1].second = 1;
				r[i][j+1].first = -1;
			}
			if (c[j] == 'R')
			{
				cr = make_pair(i,j+1);
				r[i][j+1].first = 1;
				r[i][j+1].second = -1;
			}
		}
	}
}
void write()
{
	freopen(FOUT,"w",stdout);
	printf("%d %d %d\n", tmin, mi, mj);
}
int solve()
{
	int i;
	pair <int,int> p1,p2;
	for (i = 1; i <= n; ++i)
		r[i][0].first = r[i][0].second = -2;
	for (i = 1; i <= m; ++i)
		r[0][i].first = r[0][i].second = -2;
	q.push(cr);
	while ( q.empty() == false )
	{
		p1 = q.front();
		q.pop();
		for (i = 0; i <= 7; ++i)
			if ( p1.first + dx[i] <= n && p1.second + dy[i] <= m )
				{
					p2 = make_pair( p1.first + dx[i], p1.second + dy[i]);
					if (r[p2.first][p2.second].first == -1)
					{
						r[p2.first][p2.second].first = r[p1.first][p1.second].first + 1;
						q.push(p2);
					}
				}
		
	}
	q.push(cj);
	while ( q.empty() == false )
	{
		p1 = q.front();
		q.pop();
		for (i = 0; i <= 7; ++i)
			if ( p1.first + dx[i] <= n && p1.second + dy[i] <= m )
				{
					p2 = make_pair( p1.first + dx[i], p1.second + dy[i]);
					if ( r[p2.first][p2.second].second == -1)
					{
						r[p2.first][p2.second].second = r[p1.first][p1.second].second + 1;						
						if ( r[p2.first][p2.second].first == r[p2.first][p2.second].second)
						{
							if (r[p2.first][p2.second].first < tmin)
							{
								mi = p2.first; mj = p2.second;
								tmin = r[p2.first][p2.second].first;
							}
							else if (r[p2.first][p2.second].first == tmin && (p2.first <= mi || (p2.first == mi && p2.second == mj)))
								tmin = r[p2.first][p2.second].first;
						}
						q.push(p2);
					}
				}
		
	}
	return -1;
}
int main()
{
	read();
	solve();
	write();
}