Cod sursa(job #1525545)

Utilizator hrazvanHarsan Razvan hrazvan Data 15 noiembrie 2015 11:04:43
Problema Car Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#define MAXN 500
#define DIR 8
#define INF 2000000000
#define NRND (MAXN * MAXN * DIR)
int dir[DIR][2] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
char ma[MAXN][MAXN];
int d[MAXN][MAXN][DIR];
int dq[NRND];

inline int abs(int x){
  return x < 0 ? -x : x;
}

inline void add(int *p, int x){
  (*p) += x + NRND;
  while((*p) >= NRND)
    (*p) -= NRND;
}

inline void dijkstra(int lin, int col, int n, int m){
  int st = 0, dr = 0, i, a, b, c, dc, na, nb, nc;
  for(i = 0; i < DIR; i++){
    d[lin][col][i] = 1;
    dq[dr] = (lin << 13) + (col << 4) + i;
    add(&dr, 1);
  }
  while(st != dr){
    a = dq[st] >> 13;
    b = (dq[st] >> 4) & ((1 << 9) - 1);
    c = dq[st] & ((1 << 4) - 1);
    add(&st, 1);
    na = a + dir[c][0];
    nb = b + dir[c][1];
    if(na >= 0 && na < n && nb >= 0 && nb < m && ma[na][nb] == 0 && (d[na][nb][c] == 0 || d[na][nb][c] > d[a][b][c])){
      d[na][nb][c] = d[a][b][c];
      add(&st, -1);
      dq[st] = (na << 13) + (nb << 4) + c;
    }
    for(dc = -1; dc <= 1; dc += 2){
      nc = (c + dc + 8) % 8;
      if(ma[a][b] == 0 && (d[a][b][nc] == 0 || d[a][b][nc] > d[a][b][c] + 1)){
        d[a][b][nc] = d[a][b][c] + 1;
        dq[dr] = (a << 13) + (b << 4) + nc;
        add(&dr, 1);
      }
    }
  }
}

int main(){
  FILE *in = fopen("car.in", "r");
  FILE *out = fopen("car.out", "w");
  int n, m, i, j, sl, sc, fl, fc;
  fscanf(in, "%d%d%d%d%d%d", &n, &m, &sl, &sc, &fl, &fc);
  sl--;  sc--;  fl--;  fc--;
  if(n == 0 || m == 0){
    fprintf(out, "0");
    fclose(in);
    fclose(out);
    return 0;
  }
  for(i = 0; i < n; i++)
    for(j = 0; j < m; j++)
      fscanf(in, "%d", &ma[i][j]);
  dijkstra(sl, sc, n, m);
  fclose(in);
  int min = INF;
  for(i = 0; i < DIR; i++)
    if(d[fl][fc][i] != 0 && min > d[fl][fc][i])
      min = d[fl][fc][i];
  if(min == INF)
    fprintf(out, "-1");
  else
    fprintf(out, "%d", min - 1);
  fclose(out);
  return 0;
}