Cod sursa(job #1201589)

Utilizator pulseOvidiu Giorgi pulse Data 25 iunie 2014 14:55:19
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

typedef pair <int, int> q;
const int Dx[] = {-1, -1, 0, 1, 1, 1, 0, -1},
		  Dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int Nmax = 101;
const int INF = 0x3f3f3f3f;
int N, M, Ri, Rj, Ji, Jj;
int R[Nmax][Nmax], J[Nmax][Nmax], iv, jv, sol, soli, solj;
char s[Nmax], m[Nmax][Nmax];

void read();
void solve();
bool OK(int, int);
void init(int v[Nmax][Nmax]);
void lee_R(int, int);
void lee_J(int, int);

int main()
{
	read();
	solve();
	fin.close();
	fout.close();
	return 0;
}

void solve()
{
	sol = INF;
	lee_R(Ri, Rj);
	lee_J(Ji, Jj);
	fout << sol << " " << soli << " " << solj << '\n';
}

void init(int v[Nmax][Nmax])
{
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
			v[i][j] = INF;
	}
}

void lee_R(int ii, int ji)
{
	queue <q> Q;
	Q.push(make_pair(ii, ji));
	init(R);
	R[ii][ji] = 1;
	int i, j;
	while(!Q.empty())
	{
		i = Q.front().first;
		j = Q.front().second;
		Q.pop();
		for (int d = 0; d < 8; ++d)
		{
			iv = i + Dx[d];
			jv = j + Dy[d];
			if (OK(iv, jv) && R[iv][jv] > R[i][j] + 1)
			{
				R[iv][jv] = R[i][j] + 1;
				Q.push(make_pair(iv, jv));
			}
		}
	}
}

void lee_J(int ii, int ji)
{
	queue <q> Q;
	Q.push(make_pair(ii, ji));
	init(J);
	J[ii][ji] = 1;
	int i, j;
	while (!Q.empty())
	{
		i = Q.front().first;
		j = Q.front().second;
		Q.pop();
		for (int d = 0; d < 8; ++d)
		{
			iv = i + Dx[d];
			jv = j + Dy[d];
			if (OK(iv, jv) && J[iv][jv] > J[i][j] + 1)
			{
				J[iv][jv] = J[i][j] + 1;
				Q.push(make_pair(iv, jv));

				if (J[iv][jv] == R[iv][jv] && J[iv][jv] <= sol)
				{
					if (J[iv][jv] < sol)
					{
						sol = J[iv][jv];
						soli = iv;
						solj = jv;
					}
					else
					{
						if (iv < soli)
						{
							soli = iv;
							solj = jv;
						}
						else if (iv == soli && jv < solj)
							solj = jv;
					}
				}
			}
		}
	}
}

bool OK(int i, int j)
{
	if (i < 1 || j < 1 || i > N || j > M) return 0;
	if (m[i][j] == 'X') return 0;
	return 1;
}

void read()
{
	int i, j, lg;
	fin >> N >> M;
	fin.getline(s, Nmax);
	for (i = 1; i <= N; ++i)
	{
		fin.getline(s, Nmax);
		lg = strlen(s);
		for (j = 0; j < lg; ++j)
		{
			m[i][j + 1] = s[j];
			if (m[i][j + 1] == 'R')
			{
				Ri = i;
				Rj = j + 1;
			}
			if (m[i][j + 1] == 'J')
			{
				Ji = i;
				Jj = j + 1;
			}
		}
		++j;
		while (j <= M)
		{
			m[i][j] = ' ';
			++j;
		}
	}
}