Cod sursa(job #381943)

Utilizator dacyanMujdar Dacian dacyan Data 12 ianuarie 2010 10:32:34
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <queue>
#define INF 100000
using namespace std;

struct Cell {
	int i;
	int j;
}x;

queue<Cell> Q;

int b[101][101], r[101][101], ju[101][101];
long m, n,  mini, minj;
long ipr, jpr, ipj, jpj;
long dmin = INF;

const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};

void Read();
void Write();
bool OK(int, int);

void Romeo();
void Julieta();
void Solve();

int main()
{
	Read();
	Romeo();
	Julieta();
	Solve();
	Write();
	return 0;
}

void Read()
{
	ifstream fin("rj.in");
	fin >> m >> n;
	char linie[1000];
	fin.get();
	for ( int i = 0; i < m; i++)
	{
		fin.getline(linie, 101);
		for ( int j = 0; j < n; j++)
		{
			if ( linie[j] == 'X')
				b[i][j] = 1;
			if ( linie[j] == ' ')
				b[i][j] = 0;
			if ( linie[j] == 'R')
			{
				ipr = i;
				jpr = j;
			}
			if (linie[j] == 'J')
			{
				ipj = i;
				jpj = j;
			}
			r[i][j] = INF;
			ju[i][j] = INF;
		}
	}
	fin.close();
}

void Romeo()
{
	int i, j, k, iv, jv;
	r[ipr][jpr] = 1;
	x.i = ipr, x.j = jpr;
	Q.push(x);
	while ( !Q.empty() )
	{
		x = Q.front();
		i = x.i;
		j = x.j;
		for ( k = 0; k < 8; k++)
		{
			iv = i + di[k];
			jv = j + dj[k];
			if ( OK(iv, jv) && r[iv][jv] > r[i][j] + 1)
			{
				r[iv][jv] = r[i][j] + 1;
				x.i = iv;
				x.j = jv;
				Q.push(x);
			}
		}
		Q.pop();
	}
}

void Julieta()
{
	//Q.clear();
	int i, j, k, iv, jv;
	ju[ipj][jpj] = 1;
	x.i = ipj, x.j = jpj;
	Q.push(x);
	while ( !Q.empty() )
	{
		x = Q.front();
		i = x.i;
		j = x.j;
		for ( k = 0; k < 8; k++)
		{
			iv = i + di[k];
			jv = j + dj[k];
			if ( OK(iv, jv) && ju[iv][jv] > ju[i][j] + 1)
			{
				ju[iv][jv] = ju[i][j] + 1;
				x.i = iv;
				x.j = jv;
				Q.push(x);
			}
		}
		Q.pop();
	}
}

void Solve()
{
	int i, j;
	for ( i = 0; i < m; i++)
		for ( j = 0; j < n; j++)
			if ( r[i][j] + ju[i][j] - 1 < dmin && r[i][j] == ju[i][j])
			{
				dmin = r[i][j];
				mini = i + 1;
				minj = j + 1;
			}
}		

bool OK(int i, int j)
{
	return i >= 0 && i < n && j >= 0 && j < n && !b[i][j];
}

void Write()
{
	ofstream fout("rj.out");
	fout << dmin << ' ' << mini << ' ' << minj << '\n';
	//fout << ipr << ' ' << jpr;
	fout.close();
}