Cod sursa(job #66504)
Utilizator | Data | 19 iunie 2007 14:46:49 | |
---|---|---|---|
Problema | Car | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.45 kb |
#include <stdio.h>
#define dim 512
int N, M, Xi, Yi, Xf, Yf;
int A[dim][dim], C[dim][dim];
struct nod
{ int x, y, d;
nod *next;
} *L, *E;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};
const int Cost[9][8] = {
{0, 1, 2, 3, 0, 3, 2, 1},
{1, 0, 1, 2, 3, 0, 3, 2},
{2, 1, 0, 1, 2, 3, 0, 3},
{3, 2, 1, 0, 1, 2, 3, 0},
{0, 3, 2, 1, 0, 1, 2, 3},
{3, 0, 3, 2, 1, 0, 1, 2},
{2, 3, 0, 3, 2, 1, 0, 1},
{1, 2, 3, 0, 3, 2, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0}
};
int main()
{
FILE *f = fopen("car.in", "rt");
FILE *g = fopen("car.out", "wt");
fscanf(f, "%d %d %d %d %d %d", &N, &M, &Xi, &Yi, &Xf, &Yf);
int i, j;
for(i=1; i<=N; ++i)
for(j=1; j<=M; ++j)
{
fscanf(f, "%d", &A[i][j]);
C[i][j] = 0x3f3f3f3f;
}
L = new nod;
L -> x = Xi;
L -> y = Yi;
L -> d = 8;
L -> next = NULL;
E = L;
C[Xi][Yi] = 0;
int nx, ny;
while(L)
{
for(i=0; i<8; ++i)
{
nx = L -> x + dx[i];
ny = L -> y + dy[i];
if(nx >= 1 && nx <= N && ny >= 1 && ny <= M)
if(!A[nx][ny] && C[L->x][L->y] + Cost[L->d][i] < C[nx][ny])
{
nod *p = new nod;
p -> x = nx;
p -> y = ny;
p -> d = i;
p -> next = NULL;
E -> next = p;
E = p;
C[nx][ny] = C[L->x][L->y] + Cost[L->d][i];
}
}
nod *p = L;
L = L -> next;
delete p;
}
if(C[Xf][Yf] == 0x3f3f3f3f)
fprintf(g, "-1");
else
fprintf(g, "%d", C[Xf][Yf]);
fclose(f);
fclose(g);
return 0;
}