Cod sursa(job #136385)

Utilizator mariusdrgdragus marius mariusdrg Data 15 februarie 2008 15:16:38
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>

const int maxn = 102;

char a[maxn][maxn];
int ans[2][maxn][maxn];
int st[maxn * maxn];
int N,M;
char c;
int poz,poz1;

const int x1[10] = {0,-1,-1,-1,0,1,1,1,0};
const int y1[10] = {0,-1,0,1,1,1,0,-1,-1};


int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d\n",&N,&M);
	int i,j;
	for(i = 1;i <= N; ++i)
	{
		for(j = 0;j < M; ++j)
		{
			a[i][j] = getchar();
			if (a[i][j] == '\n') break;
		}
		if (j == M) scanf("\n");
		for(;j < M; ++j)
			a[i][j] = ' ';

	}
	int nr = 1;
	for(i = 1;i <= N; ++i)
	{
		for(j = 1;j <= M; ++j)
		{
			ans[0][i][j] = -1;
			ans[1][i][j] = -1;
		}
	}
	c = 'R';
	for(;nr >= 0;--nr)
	{
		for(i = 1;i <= N; ++i)
			for(j = 0;j < M; ++j)
			{
				if (a[i][j] == c)
				{
					poz = i;
					poz1 = j;
				}
			}
		st[0] = 0;
		st[++st[0]] = poz * 100 + poz1;
		ans[nr][poz][poz1] = 0;
		for(i = 1;i <= st[0]; ++i)
		{
			int x = st[i] / 100;
			int y = st[i] % 100;
			for(j = 1;j <= 8; ++j)
			{
				if (x + x1[j] <= 0 || x + x1[j] > N || y + y1[j] < 0 || y + y1[j] >= M) continue;
				if (a[x + x1[j]][y + y1[j]] == ' ' && ans[nr][x + x1[j]][y + y1[j]] == -1)
				{
					st[++st[0]] = (x + x1[j]) * 100 + (y + y1[j]);
					ans[nr][x + x1[j]][y + y1[j]] = ans[nr][x][y] + 1;
				}
			}
		}
		c = 'J';
	}
	int pozi,pozj;
	int min = 10000;
	for(i = 1;i <= N; ++i)
		for(j = 1;j <= M; ++j)
		{
			if (min > ans[0][i][j] && ans[0][i][j] != -1 && ans[1][i][j] == ans[0][i][j])
			{
				min = ans[0][i][j];
				pozi = i;
				pozj = j + 1;
			}
		}
	printf("%d %d %d\n",min + 1,pozi,pozj);
	return 0;
}