Cod sursa(job #117264)

Utilizator diac_paulPaul Diac diac_paul Data 21 decembrie 2007 00:23:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <stdio.h>
#define NMax 105
#define INF 1000000000

FILE *fin, *fout;

long n, m, rm[NMax][NMax], jm[NMax][NMax];
char a[NMax][NMax];

long dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
long dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};

long in, sf, cx[NMax * NMax], cy[NMax * NMax];

void go(long c[NMax][NMax], long x, long y)
{
	long i;

	for (i = 0; i < 8; i++)
	{
		if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m)
		{
			if (a[x+dx[i]][y+dy[i]] != 'X' && c[x+dx[i]][y+dy[i]] > c[x][y] + 1)
			{
				c[x+dx[i]][y+dy[i]] = c[x][y] + 1;
				go(c, x+dx[i], y+dy[i]);
			}
		}
	}
}

int main()
{
	int i, ii,  j, tmin, xmin, ymin, x, y;
	fin = fopen("rj.in", "rt");
	fout = fopen("rj.out", "wt");

	fscanf(fin, "%ld %ld\n", &n, &m);

	for (i = 0; i < n; i++)
		fgets(a[i], NMax, fin);

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{

			rm[i][j] = INF;
			jm[i][j] = INF;
		}
	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (a[i][j] == 'R')
			{
				rm[i][j] = 0;

				in = sf = 0;
				cx[0] = i;
				cy[0] = j;

				while (in <= sf)
				{
					x = cx[in];
					y = cy[in];
					for (ii = 0; ii < 8; ii++)
					{
						if (x + dx[ii] >= 0 && x + dx[ii] < n && y + dy[ii] >= 0 && y + dy[ii] < m)
						{
							if (a[x+dx[ii]][y+dy[ii]] != 'X' && rm[x+dx[ii]][y+dy[ii]] > rm[x][y] + 1)
							{
								rm[x+dx[ii]][y+dy[ii]] = rm[x][y] + 1;
								sf++;
								cx[sf] = x+dx[ii];
								cy[sf] = y+dy[ii];
							}
						}
					}
					in++;
				}
			}
			if (a[i][j] == 'J')
			{
				jm[i][j] = 0;

				in = sf = 0;
				cx[0] = i;
				cy[0] = j;

				while (in <= sf)
				{
					x = cx[in];
					y = cy[in];
					for (ii = 0; ii < 8; ii++)
					{
						if (x + dx[ii] >= 0 && x + dx[ii] < n && y + dy[ii] >= 0 && y + dy[ii] < m)
						{
							if (a[x+dx[ii]][y+dy[ii]] != 'X' && jm[x+dx[ii]][y+dy[ii]] > jm[x][y] + 1)
							{
								jm[x+dx[ii]][y+dy[ii]] = jm[x][y] + 1;
								sf++;
								cx[sf] = x+dx[ii];
								cy[sf] = y+dy[ii];
							}
						}
					}
					in++;
				}
			}
		}
	}

	
	tmin = INF;

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (rm[i][j] == jm[i][j] && tmin > rm[i][j])
			{
				tmin = rm[i][j];
				xmin = i;
				ymin = j;
			}
		}
	}

	fprintf(fout, "%ld %ld %ld\n", tmin + 1, xmin + 1, ymin + 1);

	return 0;
}