Pagini recente » Cod sursa (job #686451) | Cod sursa (job #2921175) | Cod sursa (job #2776931) | Cod sursa (job #2282275) | Cod sursa (job #2271890)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
ifstream fin("car.in");
ofstream fout("car.out");
const int INF = 1e9;
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
vector < vector < int > > road;
vector < vector < int > > dist[8];
struct var {
int dir, x, y, dist;
};
int main() {
int n, m; fin >> n >> m;
int bx, by, ex, ey;
fin >> bx >> by >> ex >> ey;
--bx; --by; --ex; --ey;
road.resize(n);
for (auto &x: road) x.resize(m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
fin >> road[i][j];
}
}
if (road[bx][by] == 1 || road[ex][ey] == 1) {
fout << "-1";
exit(0);
}
for (auto &y: dist) {
y.resize(n);
for (auto &x: y) {
x.resize(m, INF);
}
}
deque < var > DQ;
for (int d = 0; d < 8; ++d) {
dist[d][bx][by] = 0;
DQ.push_back({d, bx, by, 0});
}
while(!DQ.empty()) {
auto tmp = DQ.front();
int dir = tmp.dir;
int x = tmp.x;
int y = tmp.y;
int len = tmp.dist;
DQ.pop_front();
for (int way = 0; way < 8; ++way) {
int nx = x + dx[way];
int ny = y + dy[way];
if(nx < 0 || ny < 0 || nx >= n || ny >= m || road[nx][ny] == 1) continue;
int cost = len + abs(way - dir);
if (cost < dist[way][nx][ny]) {
dist[way][nx][ny] = cost;
DQ.push_back({way, nx, ny, cost});
}
}
}
int mn = INF;
for (int i = 0; i < 8; ++i) {
mn = min(mn, dist[i][ex][ey]);
}
if(mn == INF) {
fout << "-1";
} else {
fout << mn;
}
return 0;
}