Cod sursa(job #412197)

Utilizator Anne-MarieAnghelescu Ana-Maria Anne-Marie Data 5 martie 2010 13:45:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include<fstream>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

const int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
int n,m,i,j,b[105][105],a[105][105],xa,ya,xb,yb,coada[10002][2],li,ls,gasit;

void citire ()
{
	char aux;
	f>>n>>m;
	for ( i=1; i<=n; i++ )
		for ( j=1; j<=m; j++ )
		{
			f>>aux;
			if ( aux=='R' )
				xa=i,ya=j;
			else
				if ( aux=='J' )
					xb=i,yb=j;
				else
					if ( aux=='X' )
						a[i][j]=-1;
			b[i][j]=a[i][j];
		}
}

int minim( int k, int l, int c[][105] )
{
	int z=c[k+1][l];
	if ( c[k-1][l]<z && c[k-1][l]!=-1)
		z=c[k-1][l];
	else
		if ( c[k][l+1]<z && c[k-1][l+1]!=-1)
			z=c[k][l+1];
		else
			if ( c[k][l-1]<z && c[k-1][l-1]!=-1)
				z=c[k][l-1];
			else
				if ( c[k-1][l-1]<z && c[k-1][l-1]!=-1)
					z=c[k-1][l-1];
				else
					if ( c[k-1][l+1]<z && c[k-1][l+1]!=-1)
						z=c[k-1][l+1];
					else
						if ( c[k+1][l-1]<z && c[k+1][l-1]!=-1 )
							z=c[k+1][l-1];
						else
							if ( c[k+1][l+1]<z && c[k+1][l+1]!=-1 )
								z=c[k+1][l+1];
	return z;
}

void vecin (int ii, int jj, int xint, int yint, int c[][105])
{
    li=ls=1;
    coada[1][0]=ii; coada[1][1] = jj; c[ii][jj] = 1;
    while (!c[xint][yint])
    {
        i = coada[li][0];
        j = coada[li][1];
        if ( c[i][j+1]!=-1  && c[i][j+1] == 0 )
            {c[i][j+1]=minim(i,j+1,c)+1; ls++; coada[ls][0] = i; coada[ls][1] = j+1;}
        if ( c[i][j-1]!=-1  && c[i][j-1] ==0 )
            {c[i][j-1]=minim(i,j-1,c)+1; ls++; coada[ls][0] = i; coada[ls][1] = j-1;}
        if ( c[i+1][j]!=-1 && c[i+1][j] ==0 )
            {c[i+1][j]=minim(i+1,j,c)+1; ls++; coada[ls][0] = i+1; coada[ls][1] = j;}
        if ( c[i-1][j]!=-1 && c[i-1][j] ==0  )
            {c[i-1][j]=minim(i-1,j,c)+1; ls++; coada[ls][0] = i-1; coada[ls][1] = j;}
		if ( c[i-1][j-1]!=-1 && c[i-1][j-1] ==0  )
            {c[i-1][j-1]=minim(i-1,j-1,c)+1; ls++; coada[ls][0] = i-1; coada[ls][1] = j-1;}
		if ( c[i-1][j+1]!=-1 && c[i-1][j+1] ==0  )
            {c[i-1][j+1]=minim(i-1,j+1,c)+1; ls++; coada[ls][0] = i-1; coada[ls][1] = j+1;}
		if ( c[i+1][j+1]!=-1 && c[i+1][j+1] ==0 )
            {c[i+1][j+1]=minim(i+1,j+1,c)+1; ls++; coada[ls][0] = i+1; coada[ls][1] = j+1;}
		if ( c[i+1][j-1]!=-1 && c[i+1][j-1] ==0 )
            {c[i+1][j-1]=minim(i+1,j-1,c)+1; ls++; coada[ls][0] = i+1; coada[ls][1] = j-1;}	
        li++;
    }
}
	
void bordare ()
{
	for ( j=1; j<=m; j++ )
	{
		b[0][j]=-1;
		b[n+1][j]=-1;
	}
	for ( i=1; i<=n; i++ )
	{
		b[i][0]=-1;
		b[i][m+1]=-1;
	}
}

int main()
{
	citire();
	for ( i=1; i<=n; i++ ) 
	{
		for  ( j=1; j<=m; j++ )
			g<<a[i][j]<<' ';
		g<<'\n';
	}
	bordare();
	vecin(xa,ya,xb,yb,a);
	i=1; j=1; gasit=0;
	while ( i<=n && gasit==0 )
	{
		while ( j<=m && gasit==0 )
			if ( a[i][j]!=b[i][j] )
				j++;
			else
				gasit=1;
		i++;
	}
	g<<i<<' '<<j<<' '<<a[i][j]<<'\n';
	return 0;
}