Cod sursa(job #1875318)

Utilizator antanaAntonia Boca antana Data 10 februarie 2017 22:56:34
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

#define MAXN 501
#define INF 0x3f3f3f3f

using namespace std;

struct cell{
    int d, x, y;
}node, son;

vector < cell > Q[4*MAXN*MAXN];

int n, m, dist[MAXN][MAXN][8], cost[8][8];

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

inline bool ok(int x, int y, int d){
    return (x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y][d] != -INF);
}

inline void doPrice()
{
    int i, j, x, left, right;

    for(i=0; i<8; ++i)
        for(j=0; j<5; ++j)
        {
            left = i-j;
            if(left < 0) left += 8;
            right = i+j;
            if(right > 7) right -= 8;

            cost[i][left] = cost[i][right] = j;
        }
}

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

    int ans, k, x, i, j, startx, starty, stopx, stopy, price;

    scanf("%d%d%d%d%d%d", &n, &m, &startx, &starty, &stopx, &stopy);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            scanf("%d", &x);
            for(k=0; k<8; ++k)
                dist[i][j][k] = INF * (x == 0 ? 1 : -1);
        }

    for(k=0; k<8; ++k)
        dist[startx][starty][k] = 0;

    doPrice();
    for(i=0; i<8; ++i)
    {
        son.x = startx + dx[i];
        son.y = starty + dy[i];
        if(ok(son.x, son.y, i))
        {
            dist[son.x][son.y][i] = 0;
            Q[0].push_back({i, son.x, son.y});
        }
    }

    for(i=0; i<=4*n*m; ++i)
    {
        for(k = 0; k<Q[i].size(); ++k)
        {
            node = Q[i][k];

            for(j=0; j<8; ++j)
            {
                son.x = node.x + dx[j];
                son.y = node.y + dy[j];
                son.d = j;
                price = cost[node.d][son.d];

                if(ok(son.x, son.y, j) && dist[son.x][son.y][son.d] > dist[node.x][node.y][node.d] + price)
                {
                    dist[son.x][son.y][son.d] = dist[node.x][node.y][node.d] + price;
                    Q[dist[son.x][son.y][son.d]].push_back({son.d, son.x, son.y});
                }
            }
        }
    }

    ans = dist[stopx][stopy][0];
    for(k=1; k<8; ++k)
        if(ans > dist[stopx][stopy][k]) ans = dist[stopx][stopy][k];

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

    return 0;
}