Cod sursa(job #2978870)

Utilizator LuciBBadea Lucian LuciB Data 14 februarie 2023 16:29:31
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100
#define PUT 512
#define BORDER -1
#define OBSTACOL -2
#define GOL 0
int rj[NMAX+2][NMAX+2][2]; /// o matrice pentru Romeo, si una pentru Julieta
char coadal[PUT], coadac[PUT];
int prim, ultim;
int ldir[8]={-1, -1, -1,  0, 0,  1, 1, 1};
int cdir[8]={-1,  0,  1, -1, 1, -1, 0, 1};
static inline void enqueue(int l, int c){
  coadal[ultim]=l;
  coadac[ultim]=c;
  ultim=(ultim+1)%PUT;
}
static inline void dequeue(int *l, int *c){
  (*l)=coadal[prim];
  (*c)=coadac[prim];
  prim=(prim+1)%PUT;
}
static inline int empty(){
  return (prim==ultim);
}
void lee(int n, int m, int lstart, int cstart, int pers){
  int lin, col, dist, dir;
  prim=ultim=0;
  enqueue(lstart, cstart);
  rj[lstart][cstart][pers]=1;
  do{
    dequeue(&lin, &col);
    dist=rj[lin][col][pers];
    for(dir=0; dir<8; dir++){
      if(rj[lin+ldir[dir]][col+cdir[dir]][pers]==GOL){
        enqueue(lin+ldir[dir], col+cdir[dir]);
        rj[lin+ldir[dir]][col+cdir[dir]][pers]=dist+1;
      }
    }
  }while(!empty());
}
int main(){
  int n, m, l, c, lr, cr, lj, cj, tmin, lfinal, cfinal;
  char ch;
  FILE *fin, *fout;
  fin=fopen("rj.in", "r");
  fscanf(fin, "%d%d ", &n, &m);
  for(l=0; l<n+2; l++)
    rj[l][0][0]=rj[l][m+1][0]=rj[l][0][1]=rj[l][m+1][1]=BORDER;
  for(c=0; c<m+2; c++)
    rj[0][c][0]=rj[n+1][c][0]=rj[0][c][1]=rj[n+1][c][1]=BORDER;
  lr=cr=lj=cj=0;
  for(l=1; l<=n; l++){
    for(c=1; c<=m; c++){
      ch=fgetc(fin);
      rj[l][c][0]=rj[l][c][1]=GOL;
      switch(ch){
      case ' ':
        break;
      case 'X':
        rj[l][c][0]=rj[l][c][1]=OBSTACOL;
        break;
      case 'R':
        lr=l;
        cr=c;
        break;
      case 'J':
        lj=l;
        cj=c;
      }
    }
    fgetc(fin);
  }
  fclose(fin);
  lee(n, m, lr, cr, 0); /// pentru romeo
  lee(n, m, lj, cj, 1); /// pentru julieta
  tmin=4*NMAX;
  lfinal=cfinal=0;
  /*for(l=1; l<=n; l++){
    for(c=1; c<=m; c++)
      printf("%d ", rj[l][c][0]);
    printf("\n");
  }
  printf("\n");
  for(l=1; l<=n; l++){
    for(c=1; c<=m; c++)
      printf("%d ", rj[l][c][1]);
    printf("\n");
  }*/
  for(l=1; l<=n; l++){
    for(c=1; c<=m; c++){
      if(rj[l][c][0]==rj[l][c][1] && rj[l][c][0]>0 && rj[l][c][0]<tmin){
        lfinal=l;
        cfinal=c;
        tmin=rj[l][c][0];
      }
    }
  }
  fout=fopen("rj.out", "w");
  fprintf(fout, "%d %d %d", tmin, lfinal, cfinal);
  fclose(fout);
  return 0;
}