Cod sursa(job #362250)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 8 noiembrie 2009 18:19:53
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <string.h>
#include <queue>

#define DIM 100

#define BLOCAT -1
#define NEVIZITAT -2

using namespace std;

struct punct { int l, c; };

queue<punct> q;

int n, m;
char h[DIM + 2][DIM + 2];
int a[DIM + 2][DIM + 2];

punct intalnire, r;
int tmin;

void citeste()
{
	int i;
	ifstream fi("rj.in");
	fi >> n >> m;
	for(i = 0; i <= n; ++i)
		fi.getline(h[i] + 1, DIM);
	fi.close();
}

void pregHarta()
{
	int i, j;
	punct x;
	for(i = 0; i <= n + 1; ++i)
	{
		for(j = 0; j <= m + 1; ++j)
		{
			if(i == 0 || i == n + 1 || j == 0 || j == m + 1) a[i][j] = BLOCAT;
			else if(h[i][j] == ' ') a[i][j] = NEVIZITAT;
			else if(h[i][j] == 'X') a[i][j] = BLOCAT;
			else if(h[i][j] == 'R') 
			{
				r.l = i;
				r.c = j;
				a[i][j] = NEVIZITAT;
			}
			else
			{
				x.l = i;
				x.c = j;
				a[i][j] = 1;
				q.push(x);
			}
		}
	}
}

void scrie()
{
	ofstream fo("rj.out");
	fo << tmin << " " << intalnire.l << " " << intalnire.c << "\n";
	fo.close();
}

void lee()
{
	punct e, aux;
	int i, nc, nl;
	
	int dl[] = {0, 0, -1, -1, -1, 1, 1, 1};
	int dc[] = {1, -1, 0, 1, -1, 0, 1, -1};

	while(!q.empty())
	{
		e = q.front();
		q.pop();
		for(i = 0; i < 8; ++i)
		{
			nl = e.l + dl[i];
			nc = e.c + dc[i];
			
			if(a[nl][nc] == NEVIZITAT)
			{
				a[nl][nc] = a[e.l][e.c] + 1;
				aux.l = nl;
				aux.c = nc;
				q.push(aux);
			}
		}
	}
}

void detRezultat()
{
	//det timp minim
	int tsin = a[r.l][r.c];
	tmin = tsin / 2 + 1;
	int mod = tsin % 2;
	
	//det pozitie
	int i, j;
	for(i = 1; i <= n; ++i)
	{
		for(j = 1;  j <= m; ++j)
		{
			if(a[i][j] == BLOCAT) continue;
			if(mod)
			{
				if(a[i][j] == tmin)
				{
					intalnire.l = i;
					intalnire.c = j;
					
					return;
				}
			}
			else
			{
				if(a[i][j] == tmin || a[i][j] == tmin - 1)
				{
					intalnire.l = i;
					intalnire.c = j;
					
					return;
				}
			}
		}
	}
}

int main()
{
	citeste();
	pregHarta();
	lee();
	detRezultat();
	scrie();
	return 0;
}