Cod sursa(job #136410)

Utilizator oumbraPaul Filimoon oumbra Data 15 februarie 2008 15:36:44
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.52 kb
#include <stdio.h>

#define SIZE 110

int N, M;


int R1[SIZE][SIZE];
int J1[SIZE][SIZE];
char RJ[SIZE][SIZE];

struct point
{
	int x, y;
};

point Q[SIZE*SIZE];

int Qi;

void read()
{
	int i, j;
	char c;

	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);

	scanf("%d%d", &N, &M);

	scanf("\n");


	for(i=0; i<N; i++)
	{
		for(j=0; j<M; j++)
		{
			scanf("%c", &c);

  //			R1[i][j] = c;
//			J1[i][j] = c;
			RJ[i][j] = c;
		}
		scanf("\n");
	}

}

void solve()
{

	int Rx, Ry;
	int Qx, Qy;
	int Qic, i, j;

	for(i=0; i<N; i++)
	{
		for(j=0; j<M; j++)
		{
			if(RJ[i][j] == 'R')
			{
				Rx = i;
				Ry = j;
			}
		}
	}

	Qi = 0;
	Qic = 1;

	Q[Qi].x = Rx;
	Q[Qi].y = Ry;

	R1[Rx][Ry] = 1;

	while(Qi<=Qic)
	{

		Qx = Q[Qi].x;
		Qy = Q[Qi].y;

		if(Qx > 0)
		{
			if(RJ[Qx-1][Qy] != 'X' && R1[Qx-1][Qy] == 0)
			{
				R1[Qx-1][Qy] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx-1;
				Q[Qic].y = Qy;
				Qic++;
			}
		}

		if(Qy > 0)
		{
			if(RJ[Qx][Qy-1] != 'X' && R1[Qx][Qy-1] == 0)
			{
				R1[Qx][Qy-1] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx;
				Q[Qic].y = Qy;
				Qic++;
			}
		}

		if(Qx < N-1)
		{
			if(RJ[Qx+1][Qy] != 'X' && R1[Qx+1][Qy] == 0)
			{
				R1[Qx+1][Qy] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx+1;
				Q[Qic].y = Qy;
				Qic++;
			}
		}

		if(Qy < N-1)
		{
			if(RJ[Qx][Qy+1] != 'X' && R1[Qx][Qy+1] == 0)
			{
				R1[Qx][Qy+1] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx;
				Q[Qic].y = Qy+1;
				Qic++;
			}
		}

		if(Qx > 0 && Qy > 0)
		{
			if(RJ[Qx-1][Qy-1] != 'X' && R1[Qx-1][Qy-1] == 0)
			{
				R1[Qx-1][Qy-1] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx-1;
				Q[Qic].y = Qy-1;
				Qic++;
			}
		}

		if(Qx > 0 && Qy < N-1)
		{
			if(RJ[Qx-1][Qy+1] != 'X' && R1[Qx-1][Qy+1] == 0)
			{
				R1[Qx-1][Qy+1] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx-1;
				Q[Qic].y = Qy+1;
				Qic++;
			}
		}

		if(Qx < N-1 && Qy < N-1)
		{
			if(RJ[Qx+1][Qy+1] != 'X' && R1[Qx+1][Qy+1] == 0)
			{
				R1[Qx+1][Qy+1] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx+1;
				Q[Qic].y = Qy+1;
				Qic++;
			}
		}

		if(Qx < N-1 && Qy > 0)
		{
			if(RJ[Qx+1][Qy-1] != 'X' && R1[Qx+1][Qy-1] == 0)
			{
				R1[Qx+1][Qy-1] = R1[Qx][Qy]+1;

				Q[Qic].x = Qx+1;
				Q[Qic].y = Qy-1;
				Qic++;
			}
		}

		Qi++;
	}
}

void solveJ()
{

	int Rx, Ry;
	int Qx, Qy;
	int Qic, i, j;

	for(i=0; i<N; i++)
	{
		for(j=0; j<M; j++)
		{
			if(RJ[i][j] == 'J')
			{
				Rx = i;
				Ry = j;
			}
		}
	}

	Qi = 0;
	Qic = 1;

	Q[Qi].x = Rx;
	Q[Qi].y = Ry;

	J1[Rx][Ry] = 1;

	while(Qi<=Qic)
	{

		Qx = Q[Qi].x;
		Qy = Q[Qi].y;

		if(Qx > 0)
		{
			if(RJ[Qx-1][Qy] != 'X' && J1[Qx-1][Qy] == 0)
			{
				J1[Qx-1][Qy] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx-1;
				Q[Qic].y = Qy;
				Qic++;
			}
		}

		if(Qy > 0)
		{
			if(RJ[Qx][Qy-1] != 'X' && J1[Qx][Qy-1] == 0)
			{
				J1[Qx][Qy-1] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx;
				Q[Qic].y = Qy;
				Qic++;
			}
		}

		if(Qx < N-1)
		{
			if(RJ[Qx+1][Qy] != 'X' && J1[Qx+1][Qy] == 0)
			{
				J1[Qx+1][Qy] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx+1;
				Q[Qic].y = Qy;
				Qic++;
			}
		}

		if(Qy < N-1)
		{
			if(RJ[Qx][Qy+1] != 'X' && J1[Qx][Qy+1] == 0)
			{
				J1[Qx][Qy+1] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx;
				Q[Qic].y = Qy+1;
				Qic++;
			}
		}

		if(Qx > 0 && Qy > 0)
		{
			if(RJ[Qx-1][Qy-1] != 'X' && J1[Qx-1][Qy-1] == 0)
			{
				J1[Qx-1][Qy-1] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx-1;
				Q[Qic].y = Qy-1;
				Qic++;
			}
		}

		if(Qx > 0 && Qy < N-1)
		{
			if(RJ[Qx-1][Qy+1] != 'X' && J1[Qx-1][Qy+1] == 0)
			{
				J1[Qx-1][Qy+1] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx-1;
				Q[Qic].y = Qy+1;
				Qic++;
			}
		}

		if(Qx < N-1 && Qy < N-1)
		{
			if(RJ[Qx+1][Qy+1] != 'X' && J1[Qx+1][Qy+1] == 0)
			{
				J1[Qx+1][Qy+1] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx+1;
				Q[Qic].y = Qy+1;
				Qic++;
			}
		}

		if(Qx < N-1 && Qy > 0)
		{
			if(RJ[Qx+1][Qy-1] != 'X' && J1[Qx+1][Qy-1] == 0)
			{
				J1[Qx+1][Qy-1] = J1[Qx][Qy]+1;

				Q[Qic].x = Qx+1;
				Q[Qic].y = Qy-1;
				Qic++;
			}
		}

		Qi++;
	}
}


void cleanQ()
{
	Qi = 0;
}



int main()
{
	read();
	solve();
	cleanQ();
	solveJ();

	int i, j;
	int mini, minj, min;

	min = 10000;

	for(i=0; i<N; i++)
	{
		for(j=0; j<M; j++)
		{
			if(R1[i][j] == J1[i][j] && R1[i][j] != 0)
			{
				if(min > R1[i][j])
				{
					mini = i;
					minj = j;
					min = R1[i][j];
				}
			}
		}
	}

	printf("%d %d %d\n", min, mini+1, minj+1);

	return 0;
}