Pagini recente » Statistici Arama Andrei Robert (andreiarama2) | Atasamentele paginii Profil infouser | Borderou de evaluare (job #3344952) | Cod sursa (job #2546903) | Cod sursa (job #3357119)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
// Direcțiile: N, NE, E, SE, S, SV, V, NV
int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
struct State {
int r, c, dir, cost;
bool operator>(const State& other) const {
return cost > other.cost;
}
};
ifstream in("car.in");
ofstream out("car.out");
int main() {
int N, M, Si, Sj, Fi, Fj;
if (!(in >> N >> M)) return 0;
in >> Si >> Sj >> Fi >> Fj;
// Ajustare pentru indexare de la 0
Si--; Sj--; Fi--; Fj--;
vector<vector<int>> grid(N, vector<int>(M));
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
in >> grid[i][j];
// dist[linie][coloana][directie]
vector<vector<vector<int>>> dist(N, vector<vector<int>>(M, vector<int>(8, INF)));
priority_queue<State, vector<State>, greater<State>> pq;
// Inițializare: din punctul de start se poate pleca în orice direcție cu cost 0
for (int d = 0; d < 8; ++d) {
int ni = Si + dr[d];
int nj = Sj + dc[d];
if (ni >= 0 && ni < N && nj >= 0 && nj < M && grid[ni][nj] == 0) {
dist[ni][nj][d] = 0;
pq.push({ ni, nj, d, 0 });
}
}
int min_total_cost = INF;
while (!pq.empty()) {
State curr = pq.top();
pq.pop();
if (curr.cost > dist[curr.r][curr.c][curr.dir]) continue;
if (curr.r == Fi && curr.c == Fj) {
min_total_cost = min(min_total_cost, curr.cost);
continue;
}
for (int d = 0; d < 8; ++d) {
int ni = curr.r + dr[d];
int nj = curr.c + dc[d];
if (ni >= 0 && ni < N && nj >= 0 && nj < M && grid[ni][nj] == 0) {
// Calculăm diferența de unghi (numărul de pași de 45 grade)
int diff = abs(curr.dir - d);
if (diff > 4) diff = 8 - diff; // Cea mai scurtă întoarcere
int move_cost = diff;
if (dist[ni][nj][d] > curr.cost + move_cost) {
dist[ni][nj][d] = curr.cost + move_cost;
pq.push({ ni, nj, d, dist[ni][nj][d] });
}
}
}
}
if (Si == Fi && Sj == Fj) out << 0 << endl;
else if (min_total_cost == INF) out << -1 << endl;
else out << min_total_cost << endl;
return 0;
}