Cod sursa(job #1874997)

Utilizator antanaAntonia Boca antana Data 10 februarie 2017 17:16:37
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <cstdio>
#include <queue>
#include <algorithm>

#define MAXN 501
#define INF 0x3f3f3f3f

using namespace std;

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

queue < cell > Q[MAXN*MAXN];

bool seen[MAXN][MAXN];
int n, m, dist[MAXN][MAXN];

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 d1, int d2)
{
    int x;

    if(d1 == d2) return 0;

    x = max(d2, d1) - min(d1, d2);
    if(x > 4) x = 8 - x;

    return x;
}

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

    int 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;

    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({i+1, son.x, son.y});
        }
    }

    for(i=0; i<4*MAXN*MAXN; ++i)
    {
        while(!Q[i].empty())
        {
            node = Q[i].front();
            Q[i].pop();

            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+1;
                price = doPrice(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({son.d, son.x, son.y});
                }
            }
        }
    }

    printf("-1");

    return 0;
}