Cod sursa(job #614476)

Utilizator ionutmodoModoranu Ionut-Vlad ionutmodo Data 6 octombrie 2011 17:44:25
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<fstream>
#include<iostream>
using namespace std;
int a[105][105],R[105][105],J[105][105],L,C,xr,yr,xj,yj,tmin;
short dx[] = {-1,-1,-1, 0, 1, 1, 1, 0};
short dy[] = {-1, 0, 1, 1, 1, 0,-1,-1};
struct coord
{
	int x,y,dist;
};
coord q[20000];

void Citire()
{
	int i,j;
	char s[100];
	ifstream fin("rj.in");
	
	fin>>L>>C;
	fin.get();
	
	for(i=1; i<=L; i++)
	{
		fin.getline(s,100);
		for(j=0; j<C; j++)
			
			if(s[j]==' ')	a[i][j+1] = 0;
			else if(s[j]=='X')	a[i][j+1] = 1;
				else if(s[j]=='R')	{	xr = i;	yr = j+1; }
					else	{	xj = i;	yj = j+1;	}
	}
	fin.close();
}

void Bordare()
{
	int i,j,n,m;
	n = L + 1;
	m = C + 1;
	for(i=1; i<=L; i++)
		for(j=1; j<=C; j++)
			R[i][j] = J[i][j] = 1000000;
	
	for(i=0; i<=n; i++)
		R[i][0] = J[i][0] = R[i][m] = J[i][m] = -1;
	
	for(i=0; i<=m; i++)
		R[0][i] = J[0][i] = R[n][i] = J[n][i] = -1;
}

inline bool Interior(int x, int y)
{
	return (1<=x && x<=L && 1<=y && y<= C);
}

void Romeo()
{
	int pr,ul,i,j,x,y,k,val,dist;
	pr = ul = 0;
	
	q[ul].x = xr;
	q[ul].y = yr;
	q[ul].dist = 1;
	
	while(pr<=ul)
	{
		i = q[pr].x;
		j = q[pr].y;
		dist = q[pr].dist;
		val = a[i][j] + 1;
		pr++;
		for(k=0; k<8; k++)
		{
			x = i + dx[k];
			y = j + dy[k];
			
			if(Interior(x,y))
				if(a[x][y] == 0 && val < R[x][y])
				{
					ul++;
					q[ul].x = x;
					q[ul].y = y;
					q[ul].dist = dist + 1;
					R[x][y] = val;
				}
		}
	}
}
void Julieta()
{
	int pr,ul,i,j,x,y,k,val,dist;
	pr = ul = 0;
	
	q[ul].x = xj;
	q[ul].y = yj;
	q[ul].dist = 1;
	
	while(pr<=ul)
	{
		i = q[pr].x;
		j = q[pr].y;
		dist = q[pr].dist;
		val = a[i][j] + 1;
		pr++;
		for(k=0; k<8; k++)
		{
			x = i + dx[k];
			y = j + dy[k];
			
			if(Interior(x,y))
				if(a[x][y] == 0 && val < J[x][y])
				{
					ul++;
					q[ul].x = x;
					q[ul].y = y;
					q[ul].dist = dist + 1;
					J[x][y] = val;
				}
		}
	}
}

void Afisare()
{
	int i,j,tmin=1000001;
	for(i=1; i<=L; i++)
		for(j=1; j<=C; j++)
		{
			if( R[i][j] == J[i][j] )
				if(tmin>R[i][j])
				{
					tmin = R[i][j];
					xr = i;
					yr = j;
					//folosesc xr si yr sa salvez coordonatele lui tmin
				}
		}
	
	ofstream fout("rj.out");
	fout<<tmin<<" "<<xr<<" "<<yr<<"\n";
	fout.close();
}

int main ()
{
	Citire();
	Bordare();
	Romeo();
	Julieta();
	Afisare();
	/*
	int i,j;
	for(i=1; i<=L; i++)
	{
		for(j=1; j<=C; j++)
			cout<<R[i][j]<<" ";
		cout<<'\n';
	}
	*/
	return 0;
}