Cod sursa(job #20862)

Utilizator Spike7d5Spike7d5 Spike7d5 Data 22 februarie 2007 15:43:24
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#define MAX1 505
#define MAX2 10000000
#define INF  1000000000

int abs (int a) { if (a<0) return -a; return a; }

int vireaza (int a, int b)
{
  if (abs(a-b)<=4) return abs(a-b);
  return 8-abs(a-b);
}

int main () {
const int dx[8]= {-1, -1, -1, 0, 1, 1,  1,  0};
const int dy[8]= {-1,  0,  1, 1, 1, 0, -1, -1};

int n, m, x, y, dir, xx, yy, xi, yi, xf, yf, i, j, k, sol_tmp;
int drum[MAX1][MAX1], sol[MAX1][MAX1][8];
int coada_x[MAX2], coada_y[MAX2], coada_dir[MAX2], coada_start, coada_end;

freopen ("car.in", "rt", stdin);
freopen ("car.out", "wt", stdout);

scanf ("%d%d%d%d%d%d", &n, &m, &xi, &yi, &xf, &yf);
for (i=1;i<=n;i++) for (j=1;j<=m;j++) { scanf ("%d", &drum[i][j]); for (k=0;k<8;k++) sol[i][j][k]=INF; }
for (i=0;i<=n+1;i++) { drum[i][0]=drum[i][m+1]=1; }
for (i=0;i<=m+1;i++) { drum[0][i]=drum[n+1][i]=1; }

coada_start=0;
coada_end=7;
for (i=0;i<8;i++) { coada_x[i]=xi; coada_y[i]=yi; coada_dir[i]=i; sol[xi][yi][i]=0; }
while (coada_start<=coada_end) {
  x=coada_x[coada_start];
  y=coada_y[coada_start];
  dir=coada_dir[coada_start];

  for (i=0;i<8;i++) {
    xx=x+dx[i];
    yy=y+dy[i];
    if (drum[xx][yy]==0) {
      sol_tmp=vireaza(dir, i);
      if (sol[xx][yy][i]>sol[x][y][dir]+sol_tmp) {
	sol[xx][yy][i]=sol[x][y][dir]+sol_tmp;
	coada_end++;
	coada_x[coada_end]=xx;
	coada_y[coada_end]=yy;
	coada_dir[coada_end]=i; } } }

  coada_start++;
  }

sol_tmp=INF;
for (i=0;i<8;i++) if (sol_tmp>sol[xf][yf][i]) sol_tmp=sol[xf][yf][i];
printf ("%d\n", sol_tmp);

return 0;
}