Cod sursa(job #596988)

Utilizator Smaug-Andrei C. Smaug- Data 20 iunie 2011 14:47:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <cstring>

#define MAXN 102
#define INF (1<<16)

int main(){

  freopen("rj.in", "r", stdin);
  freopen("rj.out", "w", stdout);

  int N, M, i, j, xj, yj, xr, yr, x, y, nx, ny, l, r, k, mint;
  static int R[MAXN][MAXN], J[MAXN][MAXN], Qx[MAXN*MAXN], Qy[MAXN*MAXN];
  int dx[]={-1, -1, -1, 0, 1, 1, 1, 0}, dy[]={-1, 0, 1, 1, 1, 0, -1, -1};
  char A[MAXN][MAXN];

  memset(A, 'X', sizeof(A));
  memset(R, 0, sizeof(R));
  memset(J, 0, sizeof(J));

  scanf("%d%d%*c", &N, &M);
  for(i=1; i<=N; i++){
    for(j=1; j<=M; j++){
      scanf("%c", &A[i][j]);
      if(A[i][j]=='R')
	xr=i, yr=j;
      else if(A[i][j]=='J')
	xj=i, yj=j;
    }
    scanf("%*c");
  }

  Qx[1]=xr; Qy[1]=yr; l=r=1; R[xr][yr]=1;

  while(l<=r){
    x=Qx[l];
    y=Qy[l];

    for(k=0; k<8; k++){
      nx=x+dx[k];
      ny=y+dy[k];
      if(A[nx][ny]==' ' && !R[nx][ny]){
	Qx[++r]=nx;
	Qy[r]=ny;
	R[nx][ny]=R[x][y]+1;
      }
    }

    l++;
  }

  Qx[1]=xj; Qy[1]=yj; l=r=1; J[xj][yj]=1;

  while(l<=r){
    x=Qx[l];
    y=Qy[l];

    for(k=0; k<8; k++){
      nx=x+dx[k];
      ny=y+dy[k];
      if(A[nx][ny]==' ' && !J[nx][ny]){
	Qx[++r]=nx;
	Qy[r]=ny;
	J[nx][ny]=J[x][y]+1;
      }
    }

    l++;
  }

  mint=INF;
  for(i=1; i<=N; i++)
    for(j=1; j<=M; j++)
      if(R[i][j]==J[i][j] && R[i][j]<mint && R[i][j])
	mint=R[i][j], x=i, y=j;

  printf("%d %d %d\n", mint, x, y);

  return 0;

}