Cod sursa(job #181255)

Utilizator DraStiKDragos Oprica DraStiK Data 18 aprilie 2008 08:40:06
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.11 kb
#include <stdio.h>
int a[101][101],b[101][101],r[101][101],k[101][101];
int n,m,xr,yr,xj,yj;
void read ()
{
    int i,j;
    char ch;
    scanf ("%d%d\n",&n,&m);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m+1; ++j)
        {
			scanf ("%c",&ch);
			if (ch=='\n' && j!=m+1)
			{
				ch=' ';
				++j;
			}
            switch (ch)
            {
                case ' ':
                {
                    a[i][j]=0;
                    b[i][j]=0;
                    break;
                }
				case 'X':
                {
                    a[i][j]=-1;
                    b[i][j]=-1;
                    break;
                }
                case 'R':
                {
                    xr=i;
                    yr=j;
                    break;
                }
                case 'J':
                {
                    xj=i;
                    yj=j;
                    break;
				}
			}
		}
}
void solve ()
{
	int i,j,pas=0,gasit=1;
	r[xr][yr]=1;
	while (gasit)
	{
		gasit=0;
		++pas;
		for (i=1; i<=n; ++i)
			for (j=1; j<=m; ++j)
				if (r[i][j]==pas)
				{
					if (a[i-1][j]==0 && r[i-1][j]==0 && i-1<=n && i-1>=1)
					{
						gasit=1;
						r[i-1][j]=pas+1;
						a[i][j]=-1;
					}
					if (a[i][j-1]==0 && r[i][j-1]==0 && j-1<=m && j-1>=1)
					{
						gasit=1;
						r[i][j-1]=pas+1;
						a[i][j]=-1;
					}
					if (a[i+1][j]==0 && r[i+1][j]==0 && i+1<=n && i+1>=1)
					{
						gasit=1;
						r[i+1][j]=pas+1;
						a[i][j]=-1;
					}
					if (a[i][j+1]==0 && r[i][j+1]==0 && j+1<=m && j+1>=1)
					{
						gasit=1;
						r[i][j+1]=pas+1;
						a[i][j]=-1;
					}
					if (a[i-1][j-1]==0 && r[i-1][j-1]==0 && i-1<=n && i-1>=1 && j-1<=m && j-1>=1)
					{
						gasit=1;
						r[i-1][j-1]=pas+1;
						a[i][j]=-1;
					}
					if (a[i-1][j+1]==0 && r[i+1][j+1]==0 && i-1<=n && i-1>=1 && j+1<=m && j+1>=1)
					{
						gasit=1;
						r[i-1][j+1]=pas+1;
						a[i][j]=-1;
					}
					if (a[i+1][j-1]==0 && r[i+1][j-1]==0 && i+1<=n && i+1>=1 && j-1<=m && j-1>=1)
					{
						gasit=1;
						r[i+1][j-1]=pas+1;
						a[i][j]=-1;
					}
					if (a[i+1][j+1]==0 && r[i+1][j+1]==0 && i+1<=n && i+1>=1 && j+1<=m && j+1>=1)
					{
						gasit=1;
						r[i+1][j+1]=pas+1;
						a[i][j]=-1;
					}
				}
	}
	gasit=1;
	pas=0;
	k[xj][yj]=1;
	while (gasit)
	{
		gasit=0;
		++pas;
		for (i=1; i<=n; ++i)
			for (j=1; j<=m; ++j)
				if (k[i][j]==pas)
				{
					if (b[i-1][j]==0 && k[i-1][j]==0 && i-1<=n && i-1>=1)
					{
						gasit=1;
						k[i-1][j]=pas+1;
						b[i][j]=-1;
					}
					if (b[i][j-1]==0 && k[i][j-1]==0 && j-1<=m && j-1>=1)
					{
						gasit=1;
						k[i][j-1]=pas+1;
						b[i][j]=-1;
					}
					if (b[i+1][j]==0 && k[i+1][j]==0 && i+1<=n && i+1>=1)
					{
						gasit=1;
						k[i+1][j]=pas+1;
						b[i][j]=-1;
					}
					if (b[i][j+1]==0 && k[i][j+1]==0 && j+1<=m && j+1>=1)
					{
						gasit=1;
						k[i][j+1]=pas+1;
						b[i][j]=-1;
					}
					if (b[i-1][j-1]==0 && k[i-1][j-1]==0 && i-1<=n && i-1>=1 && j-1<=m && j-1>=1)
					{
						gasit=1;
						k[i-1][j-1]=pas+1;
						b[i][j]=-1;
					}
					if (b[i-1][j+1]==0 && k[i-1][j+1]==0 && i-1<=n && i-1>=1 && j+1<=m && j+1>=1)
					{
						gasit=1;
						k[i-1][j+1]=pas+1;
						b[i][j]=-1;
					}
					if (b[i+1][j-1]==0 && k[i+1][j-1]==0 && i+1<=n && i+1>=1 && j-1<=m && j-1>=1)
					{
						gasit=1;
						k[i+1][j-1]=pas+1;
						b[i][j]=-1;
					}
					if (b[i+1][j+1]==0 && k[i+1][j+1]==0 && i+1<=n && i+1>=1 && j+1<=m && j+1>=1)
					{
						gasit=1;
						k[i+1][j+1]=pas+1;
						b[i][j]=-1;
					}
				}

	}
	int imin=0,jmin=0,min=1000000000;
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j)
			if (r[i][j]==k[i][j] && r[i][j] && r[i][j]<min)
			{
                imin=i;
                jmin=j;
                min=r[i][j];
            }
	printf ("%d %d %d",min,imin,jmin);
	/*for (i=1; i<=n; ++i)
	{
		for (j=1; j<=n; ++j)
			printf ("%d ",a[i][j]);
		printf ("\n");
	} */
}
int main ()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    read ();
    solve ();
    return 0;
}