Pagini recente » Cod sursa (job #2101685) | Cod sursa (job #435811) | Cod sursa (job #773723) | Diferente pentru problema/cuplaj1 intre reviziile 4 si 3 | Cod sursa (job #3357121)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int INF = 1e9;
// Direcțiile de deplasare (8 direcții: N, NE, E, SE, S, SV, V, NV)
const int dl[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
struct State {
int l, c, dir;
};
int N, M;
int Si, Sj, Fi, Fj;
int mat[505][505];
int dist[505][505][8];
// Funcție pentru a calcula costul schimbării de direcție
inline int get_cost(int old_dir, int new_dir) {
int diff = abs(old_dir - new_dir);
return min(diff, 8 - diff);
}
int main() {
if (!fin) return 0;
fin >> N >> M;
fin >> Si >> Sj >> Fi >> Fj;
// Indexăm de la 1 la N și 1 la M
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
fin >> mat[i][j];
for (int d = 0; d < 8; ++d) {
dist[i][j][d] = INF;
}
}
}
// Caz particular: startul este egal cu sosirea
if (Si == Fi && Sj == Fj) {
fout << 0 << "\n";
return 0;
}
// Folosim 5 cozi pentru a procesa stările în ordinea costului crescător (Dial's Algorithm simplificat)
queue<State> Q[5];
int current_dist = 0;
int states_in_queues = 0;
// Din poziția inițială putem pleca în oricare dintre cele 8 direcții cu cost 0
for (int d = 0; d < 8; ++d) {
int nxt_l = Si + dl[d];
int nxt_c = Sj + dc[d];
if (nxt_l >= 1 && nxt_l <= N && nxt_c >= 1 && nxt_c <= M && mat[nxt_l][nxt_c] == 0) {
dist[nxt_l][nxt_c][d] = 0;
Q[0].push({ nxt_l, nxt_c, d });
states_in_queues++;
}
}
int min_total_cost = INF;
// Parcurgerea algoritmului
while (states_in_queues > 0) {
int q_idx = current_dist % 5;
while (!Q[q_idx].empty()) {
State curr = Q[q_idx].front();
Q[q_idx].pop();
states_in_queues--;
// Dacă am extras o stare cu o distanță mai mare decât cea deja optimizată, o ignorăm
if (dist[curr.l][curr.c][curr.dir] < current_dist) {
continue;
}
// Am ajuns la destinație? Actualizăm minimul global
if (curr.l == Fi && curr.c == Fj) {
min_total_cost = min(min_total_cost, current_dist);
}
// Încercăm să mergem în cele 8 direcții vecine
for (int nxt_dir = 0; nxt_dir < 8; ++nxt_dir) {
int nxt_l = curr.l + dl[nxt_dir];
int nxt_c = curr.c + dc[nxt_dir];
// Verificăm limitele matricii și dacă celula este liberă
if (nxt_l >= 1 && nxt_l <= N && nxt_c >= 1 && nxt_c <= M && mat[nxt_l][nxt_c] == 0) {
int edge_cost = get_cost(curr.dir, nxt_dir);
int nxt_dist = current_dist + edge_cost;
if (nxt_dist < dist[nxt_l][nxt_c][nxt_dir]) {
dist[nxt_l][nxt_c][nxt_dir] = nxt_dist;
Q[nxt_dist % 5].push({ nxt_l, nxt_c, nxt_dir });
states_in_queues++;
}
}
}
}
current_dist++;
}
// Afișarea rezultatului
if (min_total_cost == INF) {
fout << -1 << "\n";
} else {
fout << min_total_cost << "\n";
}
return 0;
}