Cod sursa(job #136438)

Utilizator mariusdrgdragus marius mariusdrg Data 15 februarie 2008 15:57:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<stdio.h>
#include<iostream.h>

const int maxn = 112;

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)
	{
		fgets(a[i],maxn,stdin);
		for(j = 0;j < M; ++j)
			if (a[i][j] == '\n') break;
		for(;j < M; ++j) a[i][j] = ' ';
	}
	int nr = 1;
	for(i = 1;i <= N; ++i)
	{
		for(j = 0;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 * 101 + poz1;
		ans[nr][poz][poz1] = 0;
		for(i = 1;i <= st[0]; ++i)
		{
			int x = st[i] / 101;
			int y = st[i] % 101;
			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]) * 101 + (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 = 0;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;
}