Cod sursa(job #81219)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 31 august 2007 19:41:25
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 4.34 kb
#include<stdio.h>
#include<stdlib.h>




struct nod{int i,j;struct nod *next;};

struct nod *tail,*head;


void adauga(int a,int b)
{
	struct nod *Nod;
        Nod=(struct nod *) malloc(sizeof(struct nod));
        Nod->next=NULL;
	Nod->i=a;
	Nod->j=b;
	head->next=Nod;
	head=Nod;
}

void sterge()
{
	struct nod *aux;
        aux=tail->next;
	free(tail);
	tail=aux;
}




int main()
{
   int x[100][100],n,m,R[100][100],J[100][100],i,j;
   int x1,y1,x2,y2,min=32000,imin,jmin;
   FILE *f=fopen("rj.in","r");
   char s[100];

   head=(struct nod *) malloc(sizeof(struct nod));
   fscanf(f,"%i",&n);
   fscanf(f,"%i\n",&m);
   
  
  
   for(i=0;i<n;i++)
   {
           fgets(s,100,f);
	   for(j=0;j<m;j++)
	   {
             if(s[j]=='R') {x1=i;y1=j;x[i][j]=2;}
             else if(s[j]=='J') {x2=i;y2=j;x[i][j]=3;}
             else if(s[j]==' ') x[i][j]=1;
             else x[i][j]=0;


           }


}



for(i=0;i<n;i++)
{
  for(j=0;j<m;j++)
  R[i][j]=0;
  J[i][j]=0;
}



head->i=x1;
head->j=y1;
tail=head;
R[x1][y1]=1;
J[x2][y2]=1;

while(tail!=NULL)
{

 if(tail->i>=1 && R[tail->i-1][tail->j]==0 && x[tail->i-1][tail->j]!=0)
 {
 adauga(tail->i-1,tail->j);
 R[tail->i-1][tail->j]=R[tail->i][tail->j]+1;
 }

 if(tail->i<n-1 && R[tail->i+1][tail->j]==0 && x[tail->i+1][tail->j]!=0)
  {
 adauga(tail->i+1,tail->j);
 R[tail->i+1][tail->j]=R[tail->i][tail->j]+1;
  }

 if(tail->j>=1 && R[tail->i][tail->j-1]==0 && x[tail->i][tail->j-1]!=0)
 {
 adauga(tail->i,tail->j-1);
 R[tail->i][tail->j-1]=R[tail->i][tail->j]+1;
}
 if(tail->j<m-1 && R[tail->i][tail->j+1]==0 && x[tail->i][tail->j+1]!=0)
{
 adauga(tail->i,tail->j+1);
 R[tail->i][tail->j+1]=R[tail->i][tail->j]+1;
}

if(tail->i<n-1 && tail->j<m-1 && R[tail->i+1][tail->j+1]==0 && x[tail->i+1][tail->j+1]!=0)
{
 adauga(tail->i+1,tail->j+1);
 R[tail->i+1][tail->j+1]=R[tail->i][tail->j]+1;
}


if(tail->i>=1 && tail->j>=1 && R[tail->i-1][tail->j-1]==0 && x[tail->i-1][tail->j-1]!=0)
{
 adauga(tail->i-1,tail->j-1);
 R[tail->i-1][tail->j-1]=R[tail->i][tail->j]+1;
}


if(tail->i>=1 && tail->j<m-1 && R[tail->i-1][tail->j+1]==0 && x[tail->i-1][tail->j+1]!=0)
{
 adauga(tail->i-1,tail->j+1);
 R[tail->i-1][tail->j+1]=R[tail->i][tail->j]+1;
}


if(tail->i<n-1 && tail->j>=1 && R[tail->i+1][tail->j-1]==0 && x[tail->i+1][tail->j-1]!=0)
{
 adauga(tail->i+1,tail->j-1);
 R[tail->i+1][tail->j-1]=R[tail->i][tail->j]+1;
}


 sterge();
}



head=(struct nod *) malloc(sizeof(struct nod));
head->i=x2;
head->j=y2;
tail=head;


while(tail!=NULL)
{

 if(tail->i>=1 && J[tail->i-1][tail->j]==0 && x[tail->i-1][tail->j]!=0)
 {
 adauga(tail->i-1,tail->j);
 J[tail->i-1][tail->j]=J[tail->i][tail->j]+1;
 }

 if(tail->i<n-1 && J[tail->i+1][tail->j]==0 && x[tail->i+1][tail->j]!=0)
  {
 adauga(tail->i+1,tail->j);
 J[tail->i+1][tail->j]=J[tail->i][tail->j]+1;
  }

 if(tail->j>=1 && J[tail->i][tail->j-1]==0 && x[tail->i][tail->j-1]!=0)
 {
 adauga(tail->i,tail->j-1);
 J[tail->i][tail->j-1]=J[tail->i][tail->j]+1;
}
 if(tail->j<m-1 && J[tail->i][tail->j+1]==0 && x[tail->i][tail->j+1]!=0)
{
 adauga(tail->i,tail->j+1);
 J[tail->i][tail->j+1]=J[tail->i][tail->j]+1;
}

if(tail->i<n-1 && tail->j<m-1 && J[tail->i+1][tail->j+1]==0 && x[tail->i+1][tail->j+1]!=0)
{
 adauga(tail->i+1,tail->j+1);
 J[tail->i+1][tail->j+1]=J[tail->i][tail->j]+1;
}


if(tail->i>=1 && tail->j>=1 && J[tail->i-1][tail->j-1]==0 && x[tail->i-1][tail->j-1]!=0)
{
 adauga(tail->i-1,tail->j-1);
 J[tail->i-1][tail->j-1]=J[tail->i][tail->j]+1;
}


if(tail->i>=1 && tail->j<m-1 && J[tail->i-1][tail->j+1]==0 && x[tail->i-1][tail->j+1]!=0)
{
 adauga(tail->i-1,tail->j+1);
 J[tail->i-1][tail->j+1]=J[tail->i][tail->j]+1;
}


if(tail->i<n-1 && tail->j>=1 && J[tail->i+1][tail->j-1]==0 && x[tail->i+1][tail->j-1]!=0)
{
 adauga(tail->i+1,tail->j-1);
 J[tail->i+1][tail->j-1]=J[tail->i][tail->j]+1;
}


 sterge();
}

fclose(f);
f=fopen("rj.out","w");


for(i=0;i<n;i++)
{
  for(j=0;j<m;j++)
  {
  if(R[i][j]==J[i][j] && R[i][j]!=0)
  {
   if(min>R[i][j]) min=R[i][j];
  }
}
}



for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(R[i][j]==J[i][j] && R[i][j]==min)
{
imin=i;
jmin=j;
break;
}
}
}

fprintf(f,"%i %i %i",min,imin+1,jmin+1);
fclose(f);
return 0;
}