Cod sursa(job #97346)

Utilizator savimSerban Andrei Stan savim Data 6 noiembrie 2007 17:22:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long min,i,j,s,k,n,m,x1,y1,x2,y2;
long map[101][101],ro[101][101],ju[101][101];
long leer[10001][2],leej[10001][2];
int v[4]={-1,1,0,0};
int o[4]={0,0,-1,1};
char c;

int main()
{

	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);


	scanf("%ld%ld%c",&n,&m,&c);
	scanf("%c",&c);
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=m; j++)
		{

			if (c=='R')
			{
				x1=i;
				y1=j;
			}

			if (c=='J')
			{
				x2=i;
				y2=j;
			}
			if (c=='X') map[i][j]=1;
			scanf("%c",&c);
			if (c=='\n')
			{
				scanf("%c",&c);
				break;
			}
		}
	}

	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			ro[i][j]=32000;
			ju[i][j]=32000;
		}

	s=0;k=1;
	ro[x1][y1]=0;
	leer[1][0]=x1;leer[1][1]=y1;
	while (s<=k)
	{
		s++;
		for (i=0; i<=3; i++)
		{
			int x=leer[s][0]+v[i];
			int y=leer[s][1]+o[i];
			if (x>0 && x<n+1 && y>0 && y<n+1 && map[x][y]!=1 && ro[x][y]>ro[leer[s][0]][leer[s][1]])
			{
				k++;
				leer[k][0]=x;
				leer[k][1]=y;
				ro[x][y]=ro[leer[s][0]][leer[s][1]]+1;
			}
		}
	}

	s=0;k=1;
	ju[x2][y2]=0;
	leej[1][0]=x2;leej[1][1]=y2;
	while (s<=k)
	{
		s++;
		for (i=0; i<=3; i++)
		{
			int x=leej[s][0]+v[i];
			int y=leej[s][1]+o[i];
			if (x>0 && x<n+1 && y>0 && y<n+1 && map[x][y]!=1 && ju[x][y]>ju[leej[s][0]][leej[s][1]])
			{
				k++;
				leej[k][0]=x;
				leej[k][1]=y;
				ju[x][y]=ju[leej[s][0]][leej[s][1]]+1;
			}
		}
	}
	min=2000000;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			if (ro[i][j]==ju[i][j] && ro[i][j]<min) min=ro[i][j];
	k=0;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
			if (ro[i][j]==ju[i][j] && ro[i][j]==min)
			{
				printf("%ld %ld %ld\n",ro[i][j],i,j);
				k=1;
				break;
			}
		if (k) break;
	}
	return 0;
}