Cod sursa(job #981242)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 6 august 2013 16:36:46
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<stdio.h>
#include<queue>
#include<string.h>

#define NMAX 507
#define INF 1000000

using namespace std;

struct Car{
    int x, y, Dir;
};

queue < Car > q;
const short int Dx[]={1, 1, 0, -1, -1, -1, 0, 1};
const short int Dy[]={0, 1, 1,  1,  0, -1,-1,-1};
bool a[NMAX][NMAX];
int D[NMAX][NMAX][8];
short int n, m, x1, y1, x2, y2;

Car make_Car(int x, int y, int Dir){
    Car A;
    A.x = x;
    A.y = y;
    A.Dir = Dir;
    return A;
}

inline int inside(int x, int y){
    if(x >= 1 && y >= 1 && x <= n && y <= m)
        return 1;
    return 0;
}

int main(){
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            scanf("%d", &a[i][j]);
    memset(D, INF, sizeof(D));
    for(int i = 0; i < 8; ++ i)
        q.push(make_Car(x1, y1, i)), D[x1][y1][i] = 0;
    while(! q.empty()){
        Car nod = q.front();
        int xn = nod.x + Dx[nod.Dir];
        int yn = nod.y + Dy[nod.Dir];
        int d = nod.Dir;
        if(! a[xn][yn] && D[nod.x][nod.y][d] < D[xn][yn][d] && inside(xn, yn) == 1)
            D[xn][yn][d] = D[nod.x][nod.y][d], q.push(make_Car(xn, yn, d));
        d = (nod.Dir + 7) % 8;
        if(D[nod.x][nod.y][nod.Dir] + 1 < D[nod.x][nod.y][d])
            D[nod.x][nod.y][d] = D[nod.x][nod.y][nod.Dir] + 1, q.push(make_Car(nod.x, nod.y, d));
        d = (nod.Dir + 9) % 8;
        if(D[nod.x][nod.y][nod.Dir] + 1 < D[nod.x][nod.y][d])
            D[nod.x][nod.y][d] = D[nod.x][nod.y][nod.Dir] + 1, q.push(make_Car(nod.x, nod.y, d));
        q.pop();
    }
    int Min = INF;
    for(int i = 0; i < 8; ++ i)
        Min = min(Min, D[x2][y2][i]);
    if(Min == INF)
        Min = -1;
    printf("%d\n", Min);
}