Cod sursa(job #2414479)

Utilizator SemetgTemes George Semetg Data 24 aprilie 2019 16:45:12
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <iostream>
#include <deque>
using namespace std;

const string FILE_NAME = "car";
const int N_MAX { 505 };
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;
};
deque <State> q;

void init() {
    ios_base::sync_with_stdio(false);
    in.tie(0);
    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];
            
            for (int k { 0 }; k < 8; ++k)
                d[i][j][k] = INF;
        }
}

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

void insertState(const State& from, char orientation) {
    int16_t x = from.x, y = from.y;
    bool advanced { from.orientation == orientation };
    if (advanced) {
        x += dx[orientation];
        y += dy[orientation];
    }
    
    if (inside(x, y) && !a[x][y] && d[x][y][orientation] > !advanced + d[from.x][from.y][from.orientation]) {
        d[x][y][orientation] = !advanced + d[from.x][from.y][from.orientation];
        
        if (advanced)
            q.push_back({ x, y, orientation });
        else
            q.push_front({ x, y, orientation });
    }
}

void solve() {
    for (char k { 0 }; k < 8; ++k) {
        State initS { start.first, start.second, k };
        q.push_back(initS);
        d[start.first][start.second][k] = 0;
    }
    
    while (!q.empty()) {
        State state { q.front() };
        q.pop_front();
        
        int oBack { (state.orientation - 1 + 8) % 8 }, oForth { (state.orientation + 1) % 8 };
        insertState(state, oBack);
        insertState(state, oForth);
        insertState(state, state.orientation);
    }
}

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