Pagini recente » Cod sursa (job #227352) | Cod sursa (job #1026888) | Cod sursa (job #259930) | Cod sursa (job #331513) | Cod sursa (job #2414383)
#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();
}