Cod sursa(job #2049304)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 27 octombrie 2017 00:31:29
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
/**
  *  Worg
  */
#include <cstdio>
#include <vector>
#include <algorithm>

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

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 x0, y0, x1, y1;
std::vector<std::vector<int > > a;

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

void ReadInput() {
    scanf("%d%d%d%d%d%d", &N, &M, &x0, &y0, &x1, &y1);
    x0--; y0--; x1--; y1--;
    a = std::vector<std::vector<int > >(N, std::vector<int>(M));
    dp = 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++) {
            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() {
    for(int i = 0; i < kStates; i++) {
        list[0].emplace_back(x0, y0, 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();

            //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());

    int answer = kMaxInf;
    for(int i = 0; i < kStates; i++) {
        answer = std::min(answer, dp[x1][y1][i]);
    }

    if(answer == kMaxInf) {
        printf("-1\n");
    } else {
        printf("%d\n", answer);
    }
}

int main() {
    ReadInput();

    RunDP();
	return 0;
}