Cod sursa(job #748768)

Utilizator cbanu96Banu Cristian cbanu96 Data 14 mai 2012 19:07:35
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <stdio.h>

#define FILEIN "rj.in"
#define FILEOUT "rj.out"
int A[103][103];
int B[103][103];
struct punct
{
	int x;
	int y;
};
punct R,J;
FILE *fin, *fout;
int N, M, tmin, x, y;
void read()
{
	int i, j;
	char c;
	fin = fopen(FILEIN, "r");
	fscanf(fin, "%d%d", &N, &M);
	fscanf(fin, "%c", &c);
	for ( i = 1; i <= N; i++)
	{
		for ( j = 1; j <= M; j++)
		{
			A[i][j] = B[i][j] = 15000;
		}
	}
	for ( i = 1; i <= N; i++)
		A[i][0] = A[i][M+1] = -1;
	for ( i = 1; i <= M; i++)
		A[0][i] = A[N+1][i] = -1;
	for ( i = 1; i <= N; i++)
	{
		for ( j = 1; j <= M; j++)
		{
			fscanf(fin, "%c", &c);
			if(c == 'X')
				A[i][j] = B[i][j] = -1;
			if(c == 'R')
				R.x = i, R.y = j;
			if(c == 'J')
				J.x = i, J.y = j;
		}
		fscanf(fin, "%c", &c);
	}
	fclose(fin);
}

void lee(int V[103][103], punct start)
{
	punct Q[20000];
	int p,u;
	Q[0].x = start.x;
	Q[0].y = start.y;
	V[start.x][start.y] = 1;
	punct p1, p2;
	p=u=0;
	while(p<=u)
	{
		p1.x = Q[p].x; p1.y = Q[p].y;
		p2.x = p1.x + 1; p2.y = p1.y;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x - 1; p2.y = p1.y;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x; p2.y = p1.y + 1;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x; p2.y = p1.y - 1;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x + 1; p2.y = p1.y + 1;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x - 1; p2.y = p1.y + 1;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x + 1; p2.y = p1.y - 1;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p2.x = p1.x - 1; p2.y = p1.y - 1;
		if(V[p2.x][p2.y] > V[p1.x][p1.y] + 1)
		{
			V[p2.x][p2.y] = V[p1.x][p1.y] + 1;
			u++; Q[u].x = p2.x; Q[u].y = p2.y;
		}
		p++;
	}
}

void write()
{
	int i, j;
	for ( i = 1; i <= N; i++)
	{
		for ( j = 1; j <= M; j++)
		{
			if(A[i][j] == B[i][j] && A[i][j] != -1)
			{
				if(A[i][j] < tmin)
				{
					tmin = A[i][j];
					x = i, y = j;
				}
			}
		}
	}
	fout = fopen(FILEOUT, "w");
	fprintf(fout, "%d %d %d\n", tmin, x, y);
	fclose(fout);
}

int main()
{
	read();
	lee(A, R);
	lee(B, J);
	tmin = N*M+1;
	write();
	return 0;
}