Cod sursa(job #373144)

Utilizator dacyanMujdar Dacian dacyan Data 12 decembrie 2009 19:34:26
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <vector>
#define INF 10000
using namespace std;

int a[101][101], r[101][101], J[101][101];
int m, n, i, j, drmin, imin, jmin;
int ipr, jpr, ipj, jpj, x, y;

int vi[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int vj[] = {-1, 0, 1, 1, 1, 0, -1, -1};

void Citire();
void Afisare();
void Lee();
bool OK (int, int);

int main()
{
	Citire();
	Lee();
	Afisare();
	return 0;
}

void Citire()
{
	ifstream fin("rj.in");
	fin >> m >> n;
	fin.get();
	char ch;
	for ( i = 0; i < m; i++)
	{
		for ( j = 0; j < n; ++j)
		{
			r[i][j] = INF;
			J[i][j] = INF;
			ch = fin.get();
			if ( ch == '\n') ch = fin.get();
			if ( ch == ' ' ) a[i][j] = 0;
			if ( ch == 'X' ) a[i][j] = 1;
			if ( ch == 'R')
			{
				ipr = i;
				jpr = j;
			}
			if ( ch == 'J')
			{
				ipj = i;
				jpj = j;
			}
		//if ( i == 4 && j == 2) fout << ch;
		}
		
		fin.get();
	}
	
	fin.close();
}

void Lee()
{
	r[ipr][jpr] = 0;
	J[ipj][jpj] = 0;
	int pas = 0;
	int iv, jv, k;
	drmin = INF;
	
	while (pas <= m * n  )
	{
		for ( i = 0; i < m; ++i)
			for ( j = 0; j < n; ++j)
			{
				if ( a[i][j] == 0)
				{
					if ( r[i][j] == pas)
					{
						for ( k = 0; k < 8; k++)
						{
							iv = i + vi[k];
							jv = j + vj[k];
							if ( OK(iv, jv) && r[iv][jv] == INF)
								r[iv][jv] = pas + 1;
						}
					}
					if ( J[i][j] == pas)
					{
						for ( k = 0; k < 8; k++)
						{
							iv = i + vi[k];
							jv = j + vj[k];
							if ( OK(iv, jv) && J[iv][jv] == INF  )
								J[iv][jv] = pas + 1;
						}
					}
				}
				if ( r[i][j] == J[i][j] && r[i][j] != INF)
				{
					if ( r[i][j] < drmin) 
					{
						drmin = r[i][j];
						imin = i;
						jmin = j;
					}
				}
				
			}
		pas++;
	}
}
	

bool OK(int i, int j)
{
	if ( i >= 0 && j >= 0 && i < m && j < n && a[i][j] != 1)
		return true;
	return false;
}

void Afisare()
{
	ofstream fout("rj.out");
	fout << drmin + 1 << ' ' << imin + 1 << ' ' << jmin + 1 << '\n';
	fout.close();
}