Cod sursa(job #373153)

Utilizator dacyanMujdar Dacian dacyan Data 12 decembrie 2009 19:52:58
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 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");
	
	char aux[102];
	fin >> m >> n;
	fin.get();
	for(i = 0; i< m; i++)
	{       
		
		fin.getline(aux,101);
		
		for(j = 0; j < n;j++)
		{	
				
				r[i][j] = INF, J[i][j] = INF;
				if (aux[j] == ' ') a[i][j] = 0;
				if (aux[j] == 'X') a[i][j] = 1;
				
				if(aux[j] == 'R')
				{
					ipr = i;
					jpr = j;
				}
				if(aux[j] == 'J')
				{
					ipj = i;
					jpj = j;
				}
					
		}	
		//fout << aux << '\n';
	}
	//fout << ipr << ' '<< jpr;
}
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();
}