Cod sursa(job #850737)

Utilizator superman_01Avramescu Cristian superman_01 Data 8 ianuarie 2013 21:23:45
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
#include<cstdio>
#include<string.h>

FILE *fin=fopen("rj.in", "r");
FILE *fout=fopen("rj.out", "w");

using namespace std;

int n,m,xr,yr,xj,yj,mj[105][105],mr[105][105];
int l[10005],coloana[10005];

void generare()
{
	int i,j;
	char c[105];
	  fscanf(fin, "%d%d", &n, &m);
    fscanf(fin, "%c", &c);
 
    for(i=1;i<=n;i++)
    {
        fgets(c, 105, fin);
 
        for(j=0;j<=m-1;j++)
            {
                if(c [j]=='R')
                {
                    mr[i][j+1]=1;
					mj[i][j+1]=-2;
                    xr=i, yr=j+1;
 
                }
                else if(c[j]=='J')
                {
                    mr[i][j+1]=-2;
					mj[i][j+1]=1;
                    xj=i, yj=j+1;
 
                }
                else if(c[j]=='X')
 
                    mr[i][j+1]=mj[i][j+1]=-1;
 
                else if(c[j]==' ')
                    mj[i][j+1]=mr[i][j+1]=-2;
 
            }
    }
	
}

void afisare()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
    for(j=1;j<=m;j++)
      printf("%d ",mj[i][j]);
      printf("\n");
    }	  
}
void afisare_r()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
    for(j=1;j<=m;j++)
      printf("%d ",mr[i][j]);
      printf("\n");
    }	  


}
int cautare(int xnou,int ynou,int k)
{
	
	int q;
	for(q=1;q<=k;q++)
		if( (l[q]==xnou) && (coloana[q]==ynou) )
			return 0;
		
	return 1;	
}



void Lee_julieta()
{
	int i,j;
	int x,y,k;
	int xnou,ynou;
	int dx[]={-1,0,0,1,-1,1,1,-1},dy[]={0,1,-1,0,-1,-1,1,1};
	k=1;
	l[1]=xj;
	coloana[1]=yj;
	for(i=1;i<=k;i++)
	{
		x=l[i];
		y=coloana[i];
	
		for(j=0;j<=7;j++)
		{
			xnou=x+dx[j];
			ynou=y+dy[j];
			if(mj[xnou][ynou]==-2||mj[xnou][ynou]>mj[x][y])
				if(cautare(xnou,ynou,k)==1)
				
			{	
				mj[xnou][ynou]=mj[x][y]+1;
				k++;
				l[k]=xnou;
				coloana[k]=ynou;
			
			}
			
			
		}
		
	}
	
	
}

void Lee_romeo()
{
	int i,j;
	int x,k,y;
	int xnou,ynou;
	int dx[]={-1,0,0,1,-1,1,1,-1},dy[]={0,1,-1,0,-1,-1,1,1};
	k=1;
	l[1]=xr;
	coloana[1]=yr;
	for(i=1;i<=k;i++)
	{
		x=l[i];
		y=coloana[i];
	
		for(j=0;j<=7;j++)
		{
			xnou=x+dx[j];
			ynou=y+dy[j];
			if(mr[xnou][ynou]==-2||mr[xnou][ynou]>mr[x][y])
				if(cautare(xnou,ynou,k)==1)
			{	
				mr[xnou][ynou]=mr[x][y]+1;
				k++;
				l[k]=xnou;
				coloana[k]=ynou;
			
			}
				
			
		}
		
	}
	
	
}

void comparare()

{
	int i,j,l,c,timp,jmin;
	
	
	timp=2000000;
	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(mj[i][j]==mr[i][j]&&mj[i][j]!=-1&&mj[i][j]!=1&&mj[i][j]!=-2)
			{
	         
                   if(mj[i][j]<timp)

				   { 
					   timp=mj[i][j];
					   l=i;
					   c=j;
				   }		
                  					   
			}
			
	
    fprintf(fout,"%d %d %d",timp, l, c);
	    
	fclose(stdout);	
	
}
void bordare()
{
    int i,j;
    for(i=0;i<=n+1;i++)
        {
            mj[i][0]=-1;
              
      mr[i][0]=-1;
              
            mr[i][m+1]=-1;
  
			mj[i][m+1]=-1;
        }
        for(j=0;j<=m+1;j++)
            {
               mj[0][j]=-1;
                mj[n+1][j]=-1;
				
               mr[0][j]=-1;
                mr[n+1][j]=-1;
                  
        }
        mj[0][0]=-1;
              mr[0][0]=-1;
      

	
}
int main()
{
	
	generare();
	bordare();
	Lee_romeo();
	Lee_julieta();
     	comparare();
	return 0;
}