Pagini recente » Cod sursa (job #2823606) | Cod sursa (job #865312) | un_concurs_ce_concurs | Cod sursa (job #2744114) | Cod sursa (job #2414479)
#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();
}