Cod sursa(job #1875023)

Utilizator antanaAntonia Boca antana Data 10 februarie 2017 17:43:04
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <queue>
#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];

bool seen[MAXN][MAXN];
int n, m, dist[MAXN][MAXN], 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){
    return (x >= 1 && x <= n && y >= 1 && y <= m && !seen[x][y]);
}

inline int 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 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)
        {
            dist[i][j] = INF;
            scanf("%d", &x);
            if(x) seen[i][j] = 1;
        }

    dist[startx][starty] = 0;
    seen[startx][starty] = 1;

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

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

            if(node.x == stopx && node.y == stopy)
            {
                printf("%d", dist[node.x][node.y]);
                return 0;
            }

            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) && dist[son.x][son.y] > dist[node.x][node.y] + price)
                {
                    dist[son.x][son.y] = dist[node.x][node.y] + price;
                    seen[son.x][son.y] = 1;
                    Q[dist[son.x][son.y]].push_back({son.d, son.x, son.y});
                }
            }
        }
    }

    printf("-1");

    return 0;
}