Cod sursa(job #541722)

Utilizator Andesa---------- ---------- Andesa Data 25 februarie 2011 13:35:10
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.h>
#include <queue>

using namespace std;

FILE *f,*s;

struct punct
{
	int x;
	int y;
};

punct v3[10]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};

punct p1,p2;

queue <punct> v4;

int i,j,k,l,m,n,xr,yr,xj,yj,v1[105][105],v2[105][105];

char c;

void LeeR()
{
	p1.x=xr;
	p1.y=yr;
	
	v4.push(p1);
	
	while(v4.size())
	{
		p1=v4.front();
		
		v4.pop();
		
		p2=p1;
		
		for(i=0;i<=7;i++)
		{
			p1=p2;
			
			p1.x+=v3[i].x;
			p1.y+=v3[i].y;
			
			if(p1.x>=1 && p1.x<=m && p1.y>=1 && p1.y<=n && v1[p1.x][p1.y]>=0 && (v1[p2.x][p2.y]+1<v1[p1.x][p1.y] || v1[p1.x][p1.y]==0))
			{
				v1[p1.x][p1.y]=v1[p2.x][p2.y]+1;
				
				v4.push(p1);
			}	
		}	
	}	
}

void LeeJ()
{
	p1.x=xj;
	p1.y=yj;
	
	v4.push(p1);
	
	while(v4.size())
	{
		p1=v4.front();
		
		v4.pop();
		
		p2=p1;
		
		for(i=0;i<=7;i++)
		{
			p1=p2;
			
			p1.x+=v3[i].x;
			p1.y+=v3[i].y;
			
			if(p1.x>=1 && p1.x<=m && p1.y>=1 && p1.y<=n && v2[p1.x][p1.y]!=-1 && (v2[p2.x][p2.y]+1<v2[p1.x][p1.y] || v2[p1.x][p1.y]==0))
			{
				v2[p1.x][p1.y]=v2[p2.x][p2.y]+1;
				
				v4.push(p1);
			}	
		}	
	}	
}

int main()
{
	f=fopen("rj.in","r");
	s=fopen("rj.out","w");
	
	fscanf(f,"%d %d\n",&m,&n);
	
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			fscanf(f,"%c",&c);
			
			if(c=='X')
				v1[i][j]=v2[i][j]=-1;
			
			if(c=='R')
			{
				xr=i;
				yr=j;
			}	
			
			if(c=='J')
			{
				xj=i;
				yj=j;
			}	
		}	
		
		fscanf(f,"\n");
	}	
	
	LeeR();
	LeeJ();
	
	int a,b,c;
	
	a=10000;

    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(v1[i][j]>0 && v1[i][j]==v2[i][j] && v1[i][j]<a)
            {
                a=v1[i][j];
                 
                b=i;
                c=j;
            }      
        }   
    }   
 
    fprintf(s,"%d %d %d",a+1,b,c); 
	
	fclose(s);
	
	return 0;
}