Cod sursa(job #189723)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 17 mai 2008 18:38:07
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<stdio.h>

const int dx[]={-1,1,0,1,0,-1,-1,1},
	  dy[]={-1,1,1,0,-1,0,1,-1};                             

int a[101][101],b[101][101];
int n,i,j,m,xr,yr,pf,pi,_i,_j,xj,yj;
long min=500001;

void citire()
{char s[5001];
  scanf("%d %d",&n,&m);
 char c=fgetc(stdin);
 for(i=1;i<=n;i++)
   {gets(s+1);
    for(j=1;j<=m;j++)
       {
	 if(s[j]=='X') {a[i][j]=1;
			b[i][j]=1;
			}
		else if(s[j]=='R') {xr=i;
				    yr=j;
				    }
			else if(s[j]=='J'){xj=i;yj=j;}
       }


   }

}

void aflur()
{
 int x[30001],y[30001],li,lf;
 li=1;
 x[1]=xr;a[xj][yj]=1;
 y[1]=yr;lf=1;
 for(li=1;li<=lf;li++)
   {i=x[li];
    j=y[li];
    for(int k=0;k<8;k++)
      {
       _i=i+dx[k];
       _j=j+dy[k];

       if(_i==xr&&_j==yr||_i==xj&&j==yj) continue;
       if(a[_i][_j]) continue;
       if(_i<1||i>n) continue;
       if(_j<1||j>m) continue;
       lf++;
       x[lf]=_i;
       y[lf]=_j;
	a[_i][_j]=a[i][j]+1;
       }
   }
}

void afluj()
{
 int x[30001],y[30001],li,lf;
 li=1;lf=1;
 x[1]=xj;
 y[1]=yj;b[xr][yr]=0;
 for(li=1;li<=lf;li++)
   {i=x[li];
    j=y[li];
    for(int k=0;k<8;k++)
     {                  
      _i=i+dx[k];
      _j=j+dy[k];
      if(_i==xr&&_j==yr||_i==xj&&j==yj) continue;
      if(b[_i][_j]) continue;
      if(_i<1||_i>n) continue;
      if(_j<1||_j>m) continue;
      lf++;
      x[lf]=_i;
      y[lf]=_j;
      b[_i][_j]=b[i][j]+1;
      }
   }
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    if(a[i][j]==b[i][j]&&a[i][j]>1)
      {if(a[i][j]<min)
	{min=a[i][j];
	 pi=j;
	 pf=i;
	 }
      }
 printf("%d %d %d",min+1,pf,pi);


}

void solve()
{
 aflur();
 afluj();
}                  

int main()
{
  freopen("rj.in","r",stdin);
  freopen("rj.out","w",stdout);
  citire();
  solve();
  return 0;
}