Cod sursa(job #541681)

Utilizator Andesa---------- ---------- Andesa Data 25 februarie 2011 13:15:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 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]!=-1 && (v1[p2.x][p2.y]+1<v1[p1.x][p1.y] || v1[p1.x][p1.y]==0))
			{
				if(p1.x!=xr||p1.y!=yr)
					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))
			{
				if(p1.x!=xj||p1.y!=yj)
					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;
	
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(v1[i][j]==v2[i][j]&&v1[i][j]!=-1)
			{
				a=i;
				b=j;
				c=v1[i][j];
				
				break;
			}	
		}	
	}	
	
	fprintf(s,"%d %d %d",c+1,a,b);
	
	fclose(s);
	
	return 0;
}