Cod sursa(job #258183)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 14 februarie 2009 20:18:51
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define FIN "rj.in"
#define FOUT "rj.out"
#define N 177
using namespace std;
const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};
queue < pair <int,int> > q;
pair <int,int> cr,cj,r[N][N];
int n,m,tmin = N * N,mi,mj;
void read()
{
	int i,j;
	char c;
	freopen(FIN,"r",stdin);
	scanf("%d%d\n", &n, &m);
	mi = n; mj = m;
	for (i = 1; i <= n; ++i)
	{
		for ( j = 1; j <= m; ++j)
		{
			scanf("%c", &c);
			if (c == ' ')
				r[i][j].first = r[i][j].second = -1;
			if (c == 'X')
				r[i][j].first = r[i][j].second = -2;
			if (c == 'J')
			{
				cj = make_pair(i,j);
				r[i][j].second = 0;
				r[i][j].first = -1;
			}
			if (c == 'R')
			{
				cr = make_pair(i,j);
				r[i][j].first = 0;
				r[i][j].second = -1;
			}
		}
		scanf("\n");
	}
}
void write()
{
	freopen(FOUT,"w",stdout);
	printf("%d %d %d\n", tmin, mi, mj);
	/*for (i = 1; i <= n; ++i)
	{
		for (j = 1; j <= n; ++j)
			printf("(%d,%d) ",r[i][j].first,r[i][j].second);
		printf("\n");
	}*/
}
int solve()
{
	int i;
	pair <int,int> p1,p2;
	for (i = 1; i <= n; ++i)
	{
		r[i][0].first = r[i][0].second = -2;
		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 <= 3; ++i)
			//for (j = 0; j <=3; ++j)
			if ( p1.first + dx[i] <= n && p1.second + dy[i] <= n )
				{
					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 <= 3; ++i)
			if ( p1.first + dx[i] <= n && p1.second + dy[i] <= n )
				{
					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();
}