Pagini recente » Cod sursa (job #337566) | Cod sursa (job #545843) | Cod sursa (job #1043943) | Cod sursa (job #695939) | Cod sursa (job #2414405)
#include <fstream>
#include <iostream>
#include <queue>
#include <cstring>
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];
bool inQueue[N_MAX][N_MAX][8];
Pct start, stop;
int sol { INF };
struct State {
int16_t x, y;
char orientation;
};
queue <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];
}
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];
if (!inQueue[x][y][orientation]) {
q.push({ x, y, orientation });
inQueue[x][y][orientation] = true;
}
}
}
void solve() {
memset(d, 0x3f, sizeof(d));
for (char k { 0 }; k < 8; ++k) {
State initS { start.first, start.second, k };
q.push(initS);
inQueue[initS.x][initS.y][initS.orientation] = true;
d[start.first][start.second][k] = 0;
}
while (!q.empty()) {
State state { q.front() };
q.pop();
inQueue[state.x][state.y][state.orientation] = false;
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);
if (oBack != oForth)
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();
}