Cod sursa(job #362474)

Utilizator Cristi09Cristi Cristi09 Data 9 noiembrie 2009 20:41:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<fstream.h>
#include<string.h>
struct nod
{
	int x,y,val;
	nod*leg;
}*prim,*p,*q;
int a[150][150],n,m,val,b[150][150];
void adauga(int i,int j,int k);
int main()
{
	prim=new nod;q=new nod;
	prim->leg=NULL;
	q=prim;
	ifstream f("rj.in");
	f>>n>>m;
	int i,j,xr,yr,xj,yj;
	char var,v[105];

	for(i=0;i<=n+1;++i)
	for(j=0;j<=m+1;++j)
	if(i==0||j==0||i==n+1||j==n+1){a[i][j]=-2;b[i][j]=-2;}
	f.getline(v,100);
	for(i=1;i<n+1;++i)
	{
		f.getline(v,105);
		if(strlen(v)==m-1)v[strlen(v)]=' ';

		for(j=1;j<m+1;++j)
		{
		   switch(v[j-1])
		   {
		   case 'R':{
					  a[i][j]=0;b[i][j]=30000;
					  xr=i;yr=j;
					  p=new nod;
					  p->leg=NULL;prim->leg=p;
					  p->x=xr=i;p->y=yr=j;p->val=0;
					  break;
					 }
		   case 'J':{
					  a[i][j]=30000;b[i][j]=0;
					  xj=i;yj=j;
					  break;
					}
		   case 'X':{
					  a[i][j]=-2;b[i][j]=-2;
					  break;
					}
		   case ' ':{
					  a[i][j]=30000;b[i][j]=30000;
					  break;
					 }
		   }

		}

	}
	f.close();
	q=prim;int cont;
	while(prim->leg)
	{
	   p=prim->leg;
	   prim->leg=p->leg;
	   val=p->val+1;
	   i=p->x;j=p->y;
	   delete p;
	   if(prim->leg==NULL)q=prim;
	   cont=0;
	   while(cont<8)
	   {
		 switch(cont)
		 {
			case 0:{adauga(i-1,j,1);break;}
			case 1:{adauga(i+1,j,1);break;}
			case 2:{adauga(i,j+1,1);break;}
			case 3:{adauga(i,j-1,1);break;}
			case 4:{adauga(i-1,j-1,1);break;}
			case 5:{adauga(i+1,j-1,1);break;}
			case 6:{adauga(i-1,j+1,1);break;}
			case 7:{adauga(i+1,j+1,1);break;}
		 }
		 cont++;
	   }
	}

	p=new nod;
	p->x=xj;p->y=yj;
	p->leg=NULL;
	prim->leg=p;
	p->val=0;
	b[xj][yj]=0;
	q=prim;
	while(prim->leg)
	{
	   p=prim->leg;
	   prim->leg=p->leg;
	   val=p->val+1;
	   i=p->x;j=p->y;
	   delete p;
	   if(prim->leg==NULL)q=prim;
	   cont=0;
	   while(cont<8)
	   {
		 switch(cont)
		 {
			case 0:{adauga(i-1,j,2);break;}
			case 1:{adauga(i+1,j,2);break;}
			case 2:{adauga(i,j+1,2);break;}
			case 3:{adauga(i,j-1,2);break;}
			case 4:{adauga(i-1,j-1,2);break;}
			case 5:{adauga(i+1,j-1,2);break;}
			case 6:{adauga(i-1,j+1,2);break;}
			case 7:{adauga(i+1,j+1,2);break;}
		 }
		 cont++;
	   }
	}
	val=30000;

	for(i=1;i<n+1;++i)
	for(j=1;j<m+1;++j)
	  if(a[i][j]==b[i][j]&&a[i][j]<val&&a[i][j]!=-2){xr=i;yr=j;val=a[i][j];}

	ofstream g("rj.out");
	g<<val+1<<" "<<xr<<" "<<yr;
	g.close();
	return 0;
}
void adauga(int i,int j,int k)
{
   if((a[i][j]>val&&k==1)||(b[i][j]>val&&k==2))
   {
	   p=new nod;
	   p->leg=NULL;
	   q->leg=p;
	   if(k==1)a[i][j]=val;
	   else b[i][j]=val;
	   p->val=val;
	   p->x=i;
	   p->y=j;
	   q=p;
   }
}