Cod sursa(job #674742)

Utilizator IoanaMarMarussi Ioana IoanaMar Data 6 februarie 2012 18:16:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>

using namespace std;

int a[105][105],mat[105][105],l,c,xr,yr,xj,yj;
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;
};

coord q[10000];

ifstream f("rj.in");
ofstream g("rj.out");

void Romeo()
{
int pr,ul,i,j,x,y,k;
pr = ul = 0;
a[xr][yr] = 2;
q[ul].x = xr;
q[ul].y = yr;

while(pr<=ul)
{
	i = q[pr].x;
	j = q[pr].y;
	pr++;      
	for(k=0; k<8; k++)
	{
		x = i + dx[k];
		y = j + dy[k];
		if(a[x][y] == 0)
		{
			ul++;
			q[ul].x = x;
			q[ul].y = y;
			a[x][y] = a[i][j] + 1;
		}
	}
}

}

void Julieta()
{
int pr,ul,i,j,x,y,k;
pr = ul = 0;
mat[xj][yj] = 2;
q[ul].x = xj;
q[ul].y = yj;
while(pr<=ul)
{
	i = q[pr].x;
	j = q[pr].y;
	pr++;
	for(k=0; k<8; k++)
	{
		x = i + dx[k];	
		y = j + dy[k];
		if(mat[x][y] == 0)
		{
			ul++;
			q[ul].x = x;
			q[ul].y = y;
			mat[x][y] = mat[i][j] + 1;
		}
	}
}
}

int main()
{
	int i,j;
	char s[110];
	f>>l>>c;
	f.get();
	for(i=1; i<=l; i++)
	{
		f.getline(s,110);
		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;   }      
	}
	for(i=1; i<=l; i++)
		for(j=1; j<=c; j++)
			mat[i][j] = a[i][j];

int n = l + 1;
int m = c + 1; 
for(i=0; i<=n; i++)
	mat[i][0] = mat[i][m] = a[i][0] = a[i][m] = -1;
 
for(i=0; i<=m; i++)
	mat[0][i] = mat[n][i] = a[0][i] = a[n][i] = -1;

Romeo();
Julieta();

int lin=0,col=0,tmin=1000000;
for(i=1; i<=l; i++)
	for(j=1; j<=c; j++)
	{
		if(a[i][j] == mat[i][j] && a[i][j] > 1)
		{
			if(a[i][j] - 1 < tmin)
			{
				tmin = a[i][j] - 1;
				lin = i;
				col = j;

			}
		}
	}
g<<tmin<<" "<<lin<<" "<<col<<"\n";

return 0;
}