Cod sursa(job #341659)

Utilizator mlazariLazari Mihai mlazari Data 19 august 2009 08:56:33
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>

#define NMAX 102
#define INF 10003

int n,m,i,j,rx,ry,jx,jy,ix,iy,fq,lq;
int Romeo[NMAX][NMAX],Julieta[NMAX][NMAX];
int qx[NMAX*NMAX],qy[NMAX*NMAX];
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
char harta[NMAX][NMAX];

void bfs(int x,int y,int matr[NMAX][NMAX]) {
  int i,px,py;
  qx[fq=lq=0]=x;
  qy[0]=y;
  while(fq<=lq) {
    x=qx[fq];
    y=qy[fq++];
    for(i=0;i<8;i++) {
      px=x+dir[i][0];
      py=y+dir[i][1];
      if((px>0)&&(px<=n)&&(py>0)&&(py<=m)&&(harta[px][py]==' ')&&
         (matr[px][py]>matr[x][y]+1)) {
        matr[px][py]=matr[x][y]+1;
        qx[++lq]=px;
        qy[lq]=py;
      }
    }
  }
}

int main() {
  freopen("rj.in","r",stdin);
  freopen("rj.out","w",stdout);
  scanf("%d%d\n",&n,&m);
  for(i=1;i<=n;i++) fgets(harta[i]+1,NMAX,stdin);
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++) {
     switch(harta[i][j]) {
       case 'R': rx=i; ry=j; break;
       case 'J': jx=i; jy=j; break;
     }
     Romeo[i][j]=INF;
     Julieta[i][j]=INF;
   }
  Romeo[rx][ry]=1;
  Julieta[jx][jy]=1;
  bfs(rx,ry,Romeo);
  bfs(jx,jy,Julieta);
  ix=0;
  iy=0;
  Romeo[0][0]=INF;
  for(i=1;i<=n;i++)
   for(j=1;j<=m;j++)
    if((Romeo[i][j]<Romeo[ix][iy])&&(Romeo[i][j]==Julieta[i][j])) {
      ix=i;
      iy=j;
    }
  printf("%d %d %d\n",Julieta[ix][iy],ix,iy);
  return 0;
}