Cod sursa(job #362262)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 8 noiembrie 2009 18:57:10
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 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];
int b[DIM + 2][DIM + 2];


punct intalnire, rom, jul;
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] = b[i][j] = BLOCAT;
			else if(h[i][j] == ' ') a[i][j] = b[i][j] = NEVIZITAT;
			else if(h[i][j] == 'X') a[i][j] = b[i][j] = BLOCAT;
			else if(h[i][j] == 'R') 
			{
				rom.l = i;
				rom.c = j;
				a[i][j] = b[i][j] = NEVIZITAT;
			}
			else
			{
				jul.l = i;
				jul.c = j;
				a[i][j] = b[i][j] = NEVIZITAT;
			}
		}
	}
}

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

void lee(int mat[DIM + 2][DIM + 2], punct start)
{
	punct e, aux;
	int i, nc, nl;
	
	q.push(start);
	
	int dl[] = {0, 0, -1, -1, -1, 1, 1, 1};
	int dc[] = {1, -1, 0, 1, -1, 0, 1, -1};

	mat[start.l][start.c] = 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(mat[nl][nc] == NEVIZITAT)
			{
				mat[nl][nc] = mat[e.l][e.c] + 1;
				aux.l = nl;
				aux.c = nc;
				q.push(aux);
			}
		}
	}
}

void detRezultat()
{
	tmin = 1000000;
	int i, j;
	for(i = 1; i <= n; ++i)
	{
		for(j = 1;  j <= m; ++j)
		{
			if(a[i][j] <= 0) continue;
			if(a[i][j] == b[i][j] && tmin > a[i][j])
			{				
				tmin = a[i][j];
				intalnire.l = i;
				intalnire.c = j;
			}
		}
	}
	if(tmin == 1000000) while(1);
}

int main()
{
	citeste();
	pregHarta();
	lee(b, rom);
	lee(a, jul);
	detRezultat();
	scrie();
	return 0;
}