Cod sursa(job #2049313)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 27 octombrie 2017 00:51:00
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
/**
  *  Worg
  */
#include <vector>
#include <fstream>
#include <algorithm>

std::ifstream fin("car.in"); std::ofstream fout("car.out");

const int kStates = 8;
const int kMaxInf = 1e9;

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];
std::vector<std::vector<std::vector<int > > > dp, seen;
/*-------- --------*/

void ReadInput() {
    fin >> N >> M >> xs >> ys >> xf >> yf;
    xs--; ys--; xf--; yf--;
    a = std::vector<std::vector<int > >(N, std::vector<int>(M));
    dp = seen = std::vector<std::vector<std::vector<int > > >(N, std::vector<std::vector<int > >(M, std::vector<int >(kStates, kMaxInf)));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            fin >> 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) & 7;
    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(seen[newX][newY][newState] > cost + where) {
            list[where].emplace_back(newX, newY, newState, cost + where);
            seen[newX][newY][newState] = cost + where;
        }
    }

}

void RunDP() {
    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) {
                fout << cost << '\n'; 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) & 7;
            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());

    fout << "-1\n";
}

int main() {
    ReadInput();

    RunDP();
    return 0;
}