Cod sursa(job #1156093)

Utilizator donydony2009FMI - Donisan George donydony2009 Data 27 martie 2014 13:38:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<fstream>
#define NV 10001
#define N 10002
#define NE 10003
#define E 10004
#define SE 10005
#define S 10006
#define SV 10007
#define V 10008
#define START 10009
using namespace std;
struct coords{
	int x,y,lvl;
}Q1[1000],J,r,RESULT;
int m,n,len;
int A[150][150];
int first1,last1;
void push1(int x,int y,int lvl)
{
	if(last1==999)
		last1=-1;
	Q1[++last1].x=x;
	Q1[last1].y=y;
	Q1[last1].lvl=lvl;
}
void pop1(void)
{
	if(first1==999)
		first1=0;
	else
		first1++;
}
coords peek1(void)
{
	return Q1[first1];
}
void citire(void)
{
	char P[105];
	int i,j;
	ifstream f("rj.in");
	f>>m>>n;
	f.get();
	for(i=1;i<=m;i++)
	{
		
		f.getline(P,101,'\n');
		for(j=0;j<n;j++)
		{
			if(P[j]==' ')
				A[i][j+1]=1;
			if(P[j]=='X')
				A[i][j+1]=0;
			if(P[j]=='R')
			{
				r.x=i;
				r.y=j+1;
				r.lvl=0;
			}
			if(P[j]=='J')
			{
				J.x=i;
				J.y=j+1;
				J.lvl=0;
			}
		}
	}
}
void Min(int B[150][150])
{
	int i;
	coords c;
	A[r.x][r.y]=3;
	A[J.x][J.y]=1;
	while(last1!=first1-1)
	{
		c=peek1();
		//NV
		if(c.x>1&&c.y>1&&A[c.x-1][c.y-1]==1&&B[c.x-1][c.y-1]==0)
		{
			push1(c.x-1,c.y-1,c.lvl+1);
			B[c.x-1][c.y-1]=c.lvl+1;
		}
		//N
		if(c.x>1&&A[c.x-1][c.y]==1&&B[c.x-1][c.y]==0)
		{
			push1(c.x-1,c.y,c.lvl+1);
			B[c.x-1][c.y]=c.lvl+1;
		}
		//NE
		if(c.x>1&&c.y<n&&A[c.x-1][c.y+1]==1&&B[c.x-1][c.y+1]==0)
		{
			push1(c.x-1,c.y+1,c.lvl+1);
			B[c.x-1][c.y+1]=c.lvl+1;
		}
		//V
		if(c.y>1&&A[c.x][c.y-1]==1&&B[c.x][c.y-1]==0)
		{
			push1(c.x,c.y-1,c.lvl+1);
			B[c.x][c.y-1]=c.lvl+1;
		}
		//E
		if(c.y<n&&A[c.x][c.y+1]==1&&B[c.x][c.y+1]==0)
		{
			push1(c.x,c.y+1,c.lvl+1);
			B[c.x][c.y+1]=c.lvl+1;
		}
		//SV
		if(c.x<m&&c.y>1&&A[c.x+1][c.y-1]==1&&B[c.x+1][c.y-1]==0)
		{
			push1(c.x+1,c.y-1,c.lvl+1);
			B[c.x+1][c.y-1]=c.lvl+1;
		}
		//S
		if(c.x<m&&A[c.x+1][c.y]==1&&B[c.x+1][c.y]==0)
		{
			push1(c.x+1,c.y,c.lvl+1);
			B[c.x+1][c.y]=c.lvl+1;
		}
		//SE
		if(c.x<m&&c.y<n&&A[c.x+1][c.y+1]==1&&B[c.x+1][c.y+1]==0)
		{
			push1(c.x+1,c.y+1,c.lvl+1);
			B[c.x+1][c.y+1]=c.lvl+1;
		}
		pop1();
	}
}
int main(void)
{
	int B[150][150],C[150][150],minim=2000000,X,Y;
	ofstream g("rj.out");
	last1=-1;
	int Total;
	len=1;
	citire();
	push1(r.x,r.y,0);
	Min(B);
	first1=0;
	last1=-1;
	push1(J.x,J.y,0);
	Min(C);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			if(B[i][j]!=0&&B[i][j]==C[i][j]&&B[i][j]<minim)
				X=i,Y=j,minim=B[i][j];
	g<<minim+1<<" "<<X<<" "<<Y;
	
}