Cod sursa(job #323096)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 10 iunie 2009 18:36:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <stdio.h>
#define N 105
#define P 10050
int v[N][N];
const int dlin[]={-1,-1,-1,0,0,1,1,1};
const int dcol[]={-1,0,1,-1,1,-1,0,1};
int n,m,coord1_r,coord2_r,coord1_j,coord2_j,r,t;
struct bfs
{
	int a,b,cost;
};
bfs coada[P];
bfs queue[P];
char marc[N][N];
int mat[N][N];
void read()
{
	scanf("%d%d\n",&n,&m);
	char x;
	int lin=1,col=0;
	while (scanf("%c",&x)!=EOF)
	{
		if (x=='\n')
		{
			lin++;
			col=0;
			continue;
		}
		if (x=='R')
		{
			v[lin][++col]=0;
			coord1_r=lin;
			coord2_r=col;
			continue;
		}
		if (x=='J')
		{
			v[lin][++col]=0;
			coord1_j=lin;
			coord2_j=col;
			continue;
		}
		if (x=='X')
		{
			v[lin][++col]=1;
			continue;
		}
		if (x==' ')
		{
			v[lin][++col]=0;
			continue;
		}
	}
}
void bordare()
{
	int i,j;
	for (i=0; i<=N; i++)
		for (j=0; j<=N; j++)
			marc[i][j]=0;
	for (i=0; i<=n+1; i++)
	{
		marc[i][0]=1;
		marc[i][m+1]=1;
	}
	for (i=0; i<=m+1; i++)
	{
		marc[0][i]=1;
		marc[n+1][i]=1;
	}
}
void bfs_romeo()
{
	r=0;
	bordare();
	coada[++r].a=coord1_r;
	coada[r].b=coord2_r;
	coada[r].cost=0;
	marc[coada[1].a][coada[1].b]=1;
	int i,j,ok=1,ant=0,act;
	while (ok)
	{
		ok=0;
		act=r;
		for (i=ant+1; i<=act; i++)
		{
			for (j=0; j<8; j++)
			{
				if (v[coada[i].a+dlin[j]][coada[i].b+dcol[j]]==0 && marc[coada[i].a+dlin[j]][coada[i].b+dcol[j]]==0)
				{
					coada[++r].a=coada[i].a+dlin[j];
					coada[r].b=coada[i].b+dcol[j];
					mat[coada[r].a][coada[r].b]=r;
					coada[r].cost=coada[i].cost+1;
					marc[coada[i].a+dlin[j]][coada[i].b+dcol[j]]=1;
					ok=1;
				}
			}
		}
		ant=act;
	}
}
void bfs_julieta()
{
	t=0;
	bordare();
	queue[++t].a=coord1_j;
	queue[t].b=coord2_j;
	queue[t].cost=0;
	marc[queue[1].a][queue[1].b]=1;
	int i,j,ok=1,ant=0,act;
	while (ok)
	{
		ok=0;
		act=t;
		for (i=ant+1; i<=act; i++)
		{
			for (j=0; j<8; j++)
			{
				if (v[queue[i].a+dlin[j]][queue[i].b+dcol[j]]==0 && marc[queue[i].a+dlin[j]][queue[i].b+dcol[j]]==0)
				{
					queue[++t].a=queue[i].a+dlin[j];
					queue[t].b=queue[i].b+dcol[j];
					queue[t].cost=queue[i].cost+1;
					if (coada[mat[queue[t].a][queue[t].b]].cost==queue[t].cost)
					{
						printf("%d %d %d\n",queue[t].cost+1,queue[t].a,queue[t].b);
						return;
					}
					marc[queue[i].a+dlin[j]][queue[i].b+dcol[j]]=1;
					ok=1;
				}
			}
		}
		ant=act;
	}
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	read();
	bfs_romeo();
	bfs_julieta();
	return 0;
}