Cod sursa(job #130701)

Utilizator savimSerban Andrei Stan savim Data 1 februarie 2008 17:46:22
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <string.h>
#define valmax 100010
int s,p,q,i,j,k,n,m;
char a[110][110];
int ro[110][110],ju[110][110];
short int sir[100000][2];
int o[8]={-1,1,0,0,-1,-1,1,1};
int v[8]={0,0,-1,1,-1,1,-1,1};

void lee(int p, int q, char cul)
{
	 int i,j;
	 for (i=1; i<=n; i++)
		 for (j=0; j<=m-1; j++)
		 if (cul=='R')
		 {
			 if (a[i][j]=='X') ro[i][j]=-1;
			 else ro[i][j]=valmax;
		 }
		 else
		 {
			 if (a[i][j]=='X') ju[i][j]=-1;
			 else ju[i][j]=valmax;
		 }
	 if (cul=='R') ro[p][q]=1;
	 else ju[p][q]=1;
	 s=1;
	 sir[s][0]=p;sir[s][1]=q;
	 p=0;
	 while (p<s)
	 {
		   p++;
		   for (i=0; i<=7; i++)
		   {
			   int x=sir[p][0]+o[i];
			   int y=sir[p][1]+v[i];

			   if (cul=='R')
			   {
					if (0<x && x<=n && 0<y && y<=m && ro[x][y]>ro[sir[p][0]][sir[p][1]]+1)
					{
					  ro[x][y]=ro[sir[p][0]][sir[p][1]]+1;
					  s++;
					  sir[s][0]=x;
					  sir[s][1]=y;
					}
			   }
			   else
			   if (0<x && x<=n && 0<y && y<=m && ju[x][y]>ju[sir[p][0]][sir[p][1]]+1)
			   {
				  ju[x][y]=ju[sir[p][0]][sir[p][1]]+1;
				  s++;
				  sir[s][0]=x;
				  sir[s][1]=y;
			   }
		   }
	 }

} 
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);

	scanf("%d%d",&n,&m);

	
    for (i=0; i<=n; i++)
		fgets(a[i],105,stdin);

    for (i=1; i<=n; i++)
		for (j=0; j<=m-1; j++)
			if (a[i][j]=='R') lee(i,j,'R');
			else if (a[i][j]=='J') lee(i,j,'J');

	p=1;q=1;
	int min=valmax;
	for (i=1; i<=n; i++)
		for (j=0; j<=m-1; j++)
			if (ro[i][j]==ju[i][j] && ro[i][j]!=-1 && ro[i][j]<min)
			{
			   min=ro[i][j];
			   p=i;
			   q=j+1;
			}

	printf("%d %d %d\n",min,p,q);
	
	
    return 0;
}