Cod sursa(job #66504)

Utilizator raula_sanChis Raoul raula_san 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;
}