Cod sursa(job #1875334)

Utilizator antanaAntonia Boca antana Data 10 februarie 2017 23:20:44
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <cstdio>
#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>

#define MAXN 501
#define BUF (1<<17)
#define INF 0x3f3f3f3f

using namespace std;

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

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

int pos = BUF, n, m, dist[MAXN][MAXN][8], cost[8][8], d[8][5];
char buf[BUF];

FILE *fin, *fout;

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 int getInt();
inline char getChar();

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

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

            cost[i][left] = cost[i][right] = j;
            d[i][j] = left;
            d[i][5-j] = right;
        }
}

int main()
{
    fin  = fopen("car.in", "r");
    fout = fopen("car.out", "w");

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

    n = getInt();
    m = getInt();
    startx = getInt();
    starty = getInt();
    stopx = getInt();
    stopy = getInt();

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            x = getInt();
            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<4; ++j)
            {
                a = d[node.d][j];
                son.x = node.x + dx[a];
                son.y = node.y + dy[a];
                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)
        fprintf(fout, "-1");
    else fprintf(fout, "%d", ans);

    return 0;
}

inline char getChar()
{
    if(pos == BUF)
        pos = 0, fread(buf, 1, BUF, fin);
    return buf[pos++];
}

inline int getInt()
{
    int nr = 0;
    char c;

    c = getChar();
    while(!isdigit(c)) c = getChar();
    while(isdigit(c))
    {
        nr = nr*10 + c-'0';
        c = getChar();
    }

    return nr;
}