Cod sursa(job #1603553)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 17 februarie 2016 17:28:45
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500;
const int NUM_DIR = 8;
const int INF = 0x3f3f3f3f;
const int DIR[][2] = { {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} };

bool pass[MAX_N + 1][MAX_N + 1];

deque <int> Q;

int D[MAX_N + 1][MAX_N + 1][NUM_DIR];

inline
int codify(const pair <pair <int, int>, int> &state) {
    return (state.second << 18) | (state.first.second << 9) | state.first.first;
}

inline
pair <pair <int, int>, int> decode(const int &state) {
    return make_pair(make_pair(state & 511, (state >> 9) & 511), state >> 18);
}

int main() {
    ifstream fin("car.in");
    ofstream fout("car.out");
    fin.tie(0);
    fout.tie(0);
    ios_base::sync_with_stdio(false);

    int N, M;
    pair <int, int> startPos, endPos;

    fin >> N >> M >> startPos.first >> startPos.second >> endPos.first >> endPos.second;

    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= M; ++ j) {
            int x; fin >> x;
            pass[i][j] = x ^ 1;
        }
    }

    memset(D, 0x3f, sizeof(D));

    for (int i = 0; i < NUM_DIR; ++ i) {
        D[startPos.first][startPos.second][i] = 0;
        Q.push_back(codify(make_pair(startPos, i)));
    }

    while (!Q.empty()) {
        const pair< pair <int, int>, int> state = decode(Q.front());
        Q.pop_front();

        const int x = state.first.first;
        const int y = state.first.second;

        const int currentDir = state.second;

        const int cost = D[x][y][currentDir];

        for (int j = -1; j <= 1; ++ j) {
            int newDir = (currentDir + j + NUM_DIR) & 7;
            int X, Y;

            if (j == 0) {
                X = x + DIR[newDir][0];
                Y = y + DIR[newDir][1];
            } else {
                X = x;
                Y = y;
            }

            if (X <= 0 || X > N || Y > M || Y <= 0 || !pass[X][Y]) {
                continue;
            }

            if (D[X][Y][newDir] > cost + (j != 0)) {
                D[X][Y][newDir] = cost + (j != 0);
                if (j != 0) {
                    Q.push_back(codify(make_pair(make_pair(X, Y), newDir)));
                } else {
                    Q.push_front(codify(make_pair(make_pair(X, Y), newDir)));
                }
            }
        }
    }

    int minCost = INF;
    for (int i = 0; i < NUM_DIR; ++ i) {
        if (D[endPos.first][endPos.second][i] < minCost) {
            minCost = D[endPos.first][endPos.second][i];
        }
    }

    if (minCost == INF) {
        minCost = -1;
    }

    fout << minCost << '\n';
    fout.close();
    return 0;
}