Mai intai trebuie sa te autentifici.
Cod sursa(job #2921391)
Utilizator | Data | 30 august 2022 17:14:10 | |
---|---|---|---|
Problema | Car | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.74 kb |
#include <fstream>
#include <vector>
#include <tuple>
#include <deque>
using namespace std;
ifstream cin("car.in");
ofstream cout("car.out");
const int kDir = 8;
const int kMax = 2e6;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
vector<vector<vector<int>>> bfs(int n, int m, vector<vector<bool>>& harta, int xs, int ys) {
vector<vector<vector<int>>> dist(
n + 1, vector<vector<int>>(
m + 1, vector<int>(
kDir, kMax)));
deque<tuple<int, int, int>> heap;
for (int i = 0; i < kDir; i++) {
dist[xs][ys][i] = 0;
heap.push_back(make_tuple(xs, ys, i));
}
while (!heap.empty()) {
int dir, x, y;
tie(x, y, dir) = heap.front();
int cost = dist[x][y][dir];
heap.pop_front();
// merge inainte pe aceeasi directie
int new_x = x + dx[dir];
int new_y = y + dy[dir];
if (harta[new_x][new_y] && dist[new_x][new_y][dir] > cost) {
dist[new_x][new_y][dir] = cost;
heap.push_front(make_tuple(new_x, new_y, dir));
}
// schimba directia cu 45 de grade
for (int i = -1; i <= 1; i += 2) {
int new_dir = (dir + i + kDir) % kDir;
if (dist[x][y][new_dir] > cost + 1) {
dist[x][y][new_dir] = cost + 1;
heap.push_back(make_tuple(x, y, new_dir));
}
}
}
return dist;
}
int main() {
int n, m; cin >> n >> m;
int xs, ys; cin >> xs >> ys;
int xd, yd; cin >> xd >> yd;
// true = se poate trece
vector<vector<bool>> harta(n + 2, vector<bool>(m + 2, false));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int x; cin >> x;
harta[i][j] = (x == 0);
}
}
vector<vector<vector<int>>> dist = bfs(n, m, harta, xs, ys);
int ans = kMax;
for (int i = 0; i < kDir; i++) {
ans = min(ans, dist[xd][yd][i]);
}
cout << (ans == kMax ? -1 : ans) << "\n";
return 0;
}