Cod sursa(job #2049341)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 27 octombrie 2017 08:36:38
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
/**
  *  Worg
  */
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

FILE *fin = freopen("car.in", "r", stdin); FILE *fout = freopen("car.out", "w", stdout);

const int kMaxN = 500 + 1;
const int kStates = 8;
const int kMaxInf = 0x3f3f3f3f;

const std::vector<std::pair<int,int > > dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

/*-------- Structures --------*/
struct Trio {
    int a, b, state, cost;
    Trio() {}

    Trio(int _a, int _b, int _state, int _cost) {
        a = _a; b = _b; state = _state; cost = _cost;
    }
};
/*-------- Data --------*/
int N, M;
int xs, ys, xf, yf;
std::vector<std::vector<int > > a;

std::vector<Trio > list[3];
int dp[kMaxN][kMaxN][kStates];
/*-------- --------*/

void ReadInput() {
    scanf("%d%d%d%d%d%d", &N, &M, &xs, &ys, &xf, &yf);
    xs--; ys--; xf--; yf--;
    a = std::vector<std::vector<int > >(N, std::vector<int>(M));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            scanf("%d", &a[i][j]);
        }
    }
}

void Add(int x, int y, int state, int add, int cost, int where) {
    int k = state + add;
    if(k >= kStates) {
        k -= kStates;
    } else if(k < 0) {
        k += kStates;
    }

    int newState = (k + 4) % kStates;
    int newX = x + dir[k].first;
    int newY = y + dir[k].second;

    if(0 <= newX && newX < N && 0 <= newY && newY < M && a[newX][newY] == 0) {
        if(dp[newX][newY][newState] == kMaxInf) {
            list[where].emplace_back(newX, newY, newState, cost + where);
        }
    }

}

void RunDP() {
    memset(dp, kMaxInf, sizeof(dp));
    for(int i = 0; i < kStates; i++) {
        list[0].emplace_back(xs, ys, i, 0);
    }

    do {
        while(!list[0].empty()) {

            int x = list[0].back().a, y = list[0].back().b, k = list[0].back().state, cost = list[0].back().cost;
            list[0].pop_back();

            if(x == xf && y == yf) {
                printf("%d\n", cost); return;
            }

            //printf("%d %d %d %d\n", x, y, k, cost);

            if(dp[x][y][k] != kMaxInf) continue;
            dp[x][y][k] = cost;

            int nextK = (k + 4) % kStates;
            Add(x, y, nextK,  0, cost, 0);
            Add(x, y, nextK, -1, cost, 1);
            Add(x, y, nextK, +1, cost, 1);
            Add(x, y, nextK, -2, cost, 2);
            Add(x, y, nextK, +2, cost, 2);
        }

        list[0] = list[1]; list[1] = list[2]; list[2].clear();
    }while(!list[0].empty() || !list[1].empty());

    printf("-1\n");
}

int main() {
    ReadInput();

    RunDP();
    return 0;
}