Cod sursa(job #2414383)

Utilizator SemetgTemes George Semetg Data 24 aprilie 2019 15:49:10
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;

const string FILE_NAME = "car";
const int N_MAX { 503 };
const int INF { 0x3f3f3f3f };
const int16_t dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int16_t dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
using Pct = pair<int16_t, int16_t>;

ifstream in { FILE_NAME + ".in" };
ofstream out { FILE_NAME + ".out" };

int N, M;
bool a[N_MAX][N_MAX];
int d[N_MAX][N_MAX][8];
Pct start, stop;
int sol { INF };

struct State {
    int16_t x, y;
    char orientation;
};

queue<State> q;

void init() {
    in >> N >> M >> start.first >> start.second >> stop.first >> stop.second;
    
    for (int i { 1 }; i <= N; ++i)
        for (int j { 1 }; j <= M; ++j)
            in >> a[i][j];
}

inline bool inside(int i, int j) { return i > 0 && j > 0 && i <= N && j <= M; }

void insertState(const State& from, char orientation, int diff) {
    int16_t x = from.x + dx[orientation], y = from.y + dy[orientation];
    if (!inside(x, y) || a[x][y])
        return;
    
    if (d[x][y][orientation] > diff + d[from.x][from.y][from.orientation]) {
        d[x][y][orientation] = diff + d[from.x][from.y][from.orientation];
        q.push({ x, y, orientation });
    }
}

void solve() {
    for (int i { 1 }; i <= N; ++i)
        for (int j { 1 }; j <= M; ++j)
            for (int k { 0 }; k < 8; ++k)
                d[i][j][k] = INF;
    
    for (char k { 0 }; k < 8; ++k) {
        State initS { start.first, start.second, k };
        q.push(initS);
        d[start.first][start.second][k] = 0;
    }
    
    while (!q.empty()) {
        State state { q.front() };
        q.pop();
        
        for (int step { 0 }; step <= 4; ++step) {
            int oBack { state.orientation - step }, oForth { state.orientation + step };
            if (oBack < 0)
                oBack += 8;
            if (oForth > 7)
                oForth -= 8;
            
            insertState(state, oBack, step);
            insertState(state, oForth, step);
        }
    }
}

void print() {
    for (int k { 0 }; k < 8; ++k)
        sol = min(sol, d[stop.first][stop.second][k]);
    
    out << (sol == INF ? -1 : sol);
}

int main() {
    init();
    solve();
    print();
}