Cod sursa(job #1654564)

Utilizator atatomirTatomir Alex atatomir Data 17 martie 2016 11:09:17
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
/*
 * A*
 */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 555
#define maxDir 9

struct position {
    int cost;
    int x, y, dir;

    position() {}
    position(int _cost, int _x, int _y, int _dir) {
        cost = _cost;
        x = _x;
        y = _y;
        dir = _dir;
    }

    bool operator<(const position& who)const {
        return cost > who.cost;
    }
};

int defX[8] = {+1, +1, +1, 0, -1, -1, -1, 0};
int defY[8] = {-1, 0, +1, +1, +1, 0, -1, -1};
int defAng[8] = {0, 1, 2, 3, 4, 5, 6, 7};

int n, m, i, j, x;
int xs, ys, xd, yd;
bool deny[maxN][maxN];

int dist[maxN][maxN][maxDir];
priority_queue<position> H;

int ans;

int pay(int ang1, int ang2) {
    ang1 -= ang2;
    if (ang1 < 0) ang1 = -ang1;
    if (ang1 > 4) ang1 = 8 - ang1;

    return ang1;
}

int expected(int x, int y) {
    x -= xd;
    y -= yd;

    if (x < 0) x = -x;
    if (y < 0) y = -y;

    return max(x, y) / 10;
}



int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);

    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &xs, &ys, &xd, &yd);

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            scanf("%d", &x);
            if (x) deny[i][j] = true;
        }
    }

    for (i = 0; i <= n + 1; i++)
        deny[i][0] = deny[i][m + 1] = true;

    for (i = 0; i <= m + 1; i++)
        deny[0][i] = deny[n + 1][i] = true;


    //! start the engine
    for (i = 0; i < 8; i++) {
        dist[xs][ys][i] = 1 + expected(xs, ys);
        H.push(position( dist[xs][ys][i] , xs, ys, i));
    }

    while (!H.empty()) {
        position now = H.top();
        H.pop();

        if (now.x == xd && now.y == yd) {
            ans = now.cost;
            break;
        }

        if (dist[now.x][now.y][now.dir] < now.cost) continue;
        for (i = 0; i < 8; i++) {
            int xx = now.x + defX[i];
            int yy = now.y + defY[i];
            int new_pay = dist[now.x][now.y][now.dir] - expected(now.x, now.y) + pay(now.dir, defAng[i]) + expected(xx, yy);

            if (deny[xx][yy]) continue;
            if (dist[xx][yy][i] == 0 || dist[xx][yy][i] > new_pay) {
                dist[xx][yy][i] = new_pay;
                H.push(position(new_pay, xx, yy, i));
            }
        }
    }

    if (ans == 0)
        printf("-1");
    else
        printf("%d", ans - 1);


    return 0;
}