Cod sursa(job #395258)

Utilizator Anonymous1010Chilivercu Cristian Anonymous1010 Data 12 februarie 2010 17:29:20
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>
#include<values.h>
#define N 102
#define M 10000

int a[N][N],b[N][N],c[M][2],i,j,i1,j1,i2,j2,n,m,k;
int di[8]={-1,1,1,-1,-1,1,0,0};
int dj[8]={-1,-1,1,1,0,0,-1,1};
char ch;

void coada(int aux,int bux,int cux,int dux,int v[N][N])
{
	c[0][0]=aux;
	c[0][1]=bux;
    v[aux][bux]=1;

	j=0;
	k=0;

	for(;!v[cux][dux];j++)
	{
		if(j==M)
			j=0;

		for(i=0;i<=7;i++)
			if(v[c[j][0]+di[i]][c[j][1]+dj[i]]==0)
			{
				v[c[j][0]+di[i]][c[j][1]+dj[i]]=v[c[j][0]][c[j][1]]+1;
				k++;
				c[k][0]=c[j][0]+di[i];
				c[k][1]=c[j][1]+dj[i];

				if(k==M-1)
					k=-1;
			}
	}
}

void rezolva()
{
	int min=MAXINT,x,y;

	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]==b[i][j]&&a[i][j]!=-1&&a[i][j]!=0&&min>a[i][j])
			{
				min=a[i][j];
				x=i;
				y=j;
			}

	printf("%d %d %d",min,x,y);
}

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

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


	for(i=1;i<=n;i++)
	{

		a[i][0]=-1,a[0][i]=-1,a[n+1][i]=-1,a[i][m+1]=-1;
		b[i][0]=-1,b[0][i]=-1,b[n+1][i]=-1,b[i][m+1]=-1;

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

			if(ch=='\n')
            	break;

			if(ch=='R')
			{
				i1=i;
				j1=j;
			}
			else
			{
				if(ch=='J')
				{
					i2=i;
					j2=j;
				}
				else
				{
					if(ch=='X')
					{
						a[i][j]=-1;
						b[i][j]=-1;
					}
				}
			}
		}
	}

	a[0][0]=-1,a[0][m+1]=-1,a[n+1][0]=-1,a[n+1][m+1]=-1;
	b[0][0]=-1,b[0][m+1]=-1,b[n+1][0]=-1,b[n+1][m+1]=-1;

	coada(i1,j1,i2,j2,a);
	coada(i2,j2,i1,j1,b);

	rezolva();

	return 0;
}