Cod sursa(job #1173873)

Utilizator xtreme77Patrick Sava xtreme77 Data 21 aprilie 2014 00:06:12
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 105
int dx[]={0, 1, 1, 1, 0, -1, -1, -1};
int dy[]={1, 1, 0, -1, -1, -1, 0, 1};
int mat[MAX][MAX], matJ[MAX][MAX], p, u, n, m, tmin=MAX*MAX, pozx, pozy;
struct poz{
	int x, y;
} q[MAX*MAX];

int main()
{
	char c[MAX];
	int i,j, x, y, t, d, ok=0;
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	scanf("%d %d", &n, &m);
	gets(c);
	for(i=1; i<=n; i++)
	{
		gets(c);

		for(j=0; j<strlen(c); j++)
		{
			if(c[j]=='X')
				mat[i][j+1]=-1;
			if(c[j]=='R')
			{mat[i][j+1]=1; q[u].x = i; q[u++].y = j+1; }
			if(c[j]=='J')
			{ mat[i][j+1]=1; q[u].x = i; q[u++].y = j+1;}
		}
	}
	for(i=0; i<=m+1; i++)
		mat[0][i] = mat[n+1][i] = -1;
	for(i=0; i<=n+1; i++)
		mat[i][0] = mat[i][m+1] = -1;
	for(i=0; i<=n+1; i++)
		for(j=0; j<=m+1; j++)
			matJ[i][j] = mat[i][j];
	p=1;u=1;
	mat[q[0].x][q[0].y] = 0;
	matJ[q[1].x][q[1].y] = 0;
	while(p<=u)
	{
		x = q[p].x; y = q[p].y; t = mat[x][y];
		p++;
		for(d=0; d<=7; d++)
		{
			if(mat[x+dx[d]][y+dy[d]]==0)
			{u++;q[u].x = x+dx[d]; q[u].y = y+dy[d]; mat[x+dx[d]][y+dy[d]]=t+1;}
		}
	}
	p=0;u=0;
	while(p<=u)
	{
		x = q[p].x; y = q[p].y; t = matJ[x][y];
		p++;
		for(d=0; d<=7; d++)
		{
			if(matJ[x+dx[d]][y+dy[d]]==0)
			{u++;q[u].x = x+dx[d]; q[u].y = y+dy[d]; matJ[x+dx[d]][y+dy[d]]=t+1;}
		}
	}
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(mat[i][j]==matJ[i][j] and mat[i][j]> 1 and mat[i][j]<tmin)
			{tmin = mat[i][j]; pozx = i; pozy=j;}
	printf("%d %d %d\n",tmin,pozx,pozy );
}