Cod sursa(job #1481728)

Utilizator stoianmihailStoian Mihail stoianmihail Data 5 septembrie 2015 09:10:10
Problema Rj Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <stdio.h>

#define INFTY 0x3f3f3f3f
#define MAX_Q 11025
#define Nadejde 110
#define MAX_DIR 8
#define NIL -1

typedef struct {
  int l, c, p;
} elem;

typedef struct {
  int d, p;
} cell;

int N, M, L, C;
char s[Nadejde];                     // citim o linie.
int type[Nadejde];                   // type[i] este ordinul caracterului "i".
elem Q[MAX_Q + 1];                   // coada lee().
elem romeo, juliet;                  // coordonatele lui romeo si julietei.
int time, qhead, qtail;
cell verr[Nadejde + 2][Nadejde + 2]; // matricea noastra bordata.
int delta[MAX_DIR][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {-1, 1}, {1, 1}, {1, -1}};

/** Initializeaza "type". **/
void init() {
  type['X'] = NIL;
  type['R'] = type['J'] = 1;
}

/** Pune in coada (l, c) cu personajul "p". **/
void enqueue(int l, int c, int p) {
  Q[qtail].l = l;
  Q[qtail].c = c;
  Q[qtail++].p = p;
}

/** Ia din coada urmatorul element. **/
void dequeue(int *l, int *c, int *p) {
  (*l) = Q[qhead].l;
  (*c) = Q[qhead].c;
  (*p) = Q[qhead++].p;
}

/** Bordeaza matricea. **/
void overflow(int n, int m) {
  int i, j;
  for (i = 0; i <= n; i++) {
    verr[i][0].d = verr[i][m].d = NIL;
  }
  for (j = 0; j <= m; j++) {
    verr[0][j].d = verr[n][j].d = NIL;
  }
}

/** Determina timpul minim pentru intalnire. **/
void lee() {
  int i, l, c, l0, c0, curr, dist;

  overflow(N + 1, M + 1);
  enqueue(romeo.l, romeo.c, 0);
  verr[romeo.l][romeo.c].p = 0;
  enqueue(juliet.l, juliet.c, 1);
  verr[juliet.l][juliet.c].p = 1;

  time = L = C = INFTY;
  do {
    dequeue(&l, &c, &curr);
    dist = verr[l][c].d + 1;
    /* Probeaza vecinii. */
    for (i = 0; i < MAX_DIR; i++) {
      l0 = l + delta[i][0];
      c0 = c + delta[i][1];
      /* Element inca neexplorat. */
      if (!verr[l0][c0].d) {
        verr[l0][c0].d = dist;
        verr[l0][c0].p = curr;
        enqueue(l0, c0, curr);
      /* Element explorat de partener? */
      } else if ((verr[l0][c0].d == dist) && (verr[l0][c0].p != curr)) {
        if (dist < time) {
          time = dist;
          L = l0, C = c0;
        } else if (dist == time) {
          if (l0 < L) {
            L = l0, C = c0;
          } else if ((l0 == L) && (c0 < C)) {
            C = c0;
          }
        }
      }
    }
  /* Cat timp coada nu e goala. */
  } while (qhead != qtail);
}

int main(void) {
  int i, j, c;
  FILE *f = fopen("rj.in", "r");

  /* Citeste harta orasului Verona. */
  fscanf(f, "%d %d\n", &N, &M);
  init();
  for (i = 1; i <= N; i++) {
    fgets(s + 1, Nadejde, f);
    for (j = 1; j <= M; j++) {
      c = s[j];
      verr[i][j].d = type[c];
      if (c == 'R') {
        romeo.l = i, romeo.c = j;
      } else if (c == 'J') {
        juliet.l = i, juliet.c = j;
      }
    }
  }
  fclose(f);

  f = fopen("rj.out", "w");

  lee();

  fprintf(f, "%d %d %d\n", time, L, C);
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}