Cod sursa(job #341657)

Utilizator mlazariLazari Mihai mlazari Data 19 august 2009 08:52:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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+3000],qy[NMAX*NMAX+3000];
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=jx;
  iy=jy;
  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;
}