Cod sursa(job #981238)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 6 august 2013 16:29:45
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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 int Dx[]={1, 1, 0, -1, -1, -1, 0, 1};
const int Dy[]={0, 1, 1,  1,  0, -1,-1,-1};
int a[NMAX][NMAX], D[NMAX][NMAX][8];
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)
        if(! a[x1 + Dx[i]][y1 + Dy[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;
        int x = nod.x;
        int y = nod.y;
        if(! a[xn][yn] && D[x][y][d] < D[xn][yn][d] && inside(xn, yn) == 1)
            D[xn][yn][d] = D[x][y][d], q.push(make_Car(xn, yn, d));
        d = (nod.Dir + 7) % 8;
        if(D[x][y][nod.Dir] + 1 < D[x][y][d])
            D[x][y][d] = D[x][y][nod.Dir] + 1, q.push(make_Car(x, y, d));
        d = (nod.Dir + 9) % 8;
        if(D[x][y][nod.Dir] + 1 < D[x][y][d])
            D[x][y][d] = D[x][y][nod.Dir] + 1, q.push(make_Car(x, y, d));
        q.pop();
    }
    int Min = INF;
    for(int i = 0; i < 8; ++ i)
        Min = min(Min, (int)D[x2][y2][i]);
    if(Min == INF)
        Min = -1;
    printf("%d\n", Min);
}