Pagini recente » Cod sursa (job #1014587) | Cod sursa (job #1847295) | Cod sursa (job #223176) | Cod sursa (job #1550214) | Cod sursa (job #2493851)
#include <bits/stdc++.h>
#define Nmax 550
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, xs, ys, xf, yf, dist[Nmax][Nmax][8];
bool mat[Nmax][Nmax];
struct point {
int x, y, dir, cost;
};
deque <point> Coada;
void read()
{
f >> n >> m >> xs >> ys >> xf >> yf;
--xs; --ys; --xf; --yf;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
f >> mat[i][j];
}
}
void solve()
{
if (mat[xs][ys] == 1 || mat[xf][yf] == 1) {
g << "-1";
return;
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < 8; ++k) {
dist[i][j][k] = INT_MAX;
}
for (int i = 0; i < 8; ++i) {
dist[xs][ys][i] = 0;
Coada.push_back({xs, ys, i, 0});
}
int trans[8][3];
for (int i = 0; i < 8; ++i)
for (int j = 0; j < 3; ++j) {
trans[i][j] = (7 + i + j) % 8;
}
point pos;
while (!Coada.empty()) {
pos = Coada.front();
Coada.pop_front();
if (pos.cost > dist[pos.x][pos.y][pos.dir]) continue;
for (int i = 0; i < 3; ++i) {
int xn = pos.x + dx[trans[pos.dir][i]];
int yn = pos.y + dy[trans[pos.dir][i]];
int cost = (i != 1) + pos.cost;
if (cost < dist[pos.x][pos.y][trans[pos.dir][i]]) {
dist[pos.x][pos.y][trans[pos.dir][i]] = cost;
Coada.push_back({pos.x, pos.y, trans[pos.dir][i], cost});
}
if (xn == -1 || yn == -1 || xn == n || yn == m || mat[xn][yn]) continue;
if (cost < dist[xn][yn][trans[pos.dir][i]]) {
dist[xn][yn][trans[pos.dir][i]] = cost;
if (i == 1)
Coada.push_front({xn, yn, trans[pos.dir][i], cost});
else
Coada.push_back({xn, yn, trans[pos.dir][i], cost});
}
}
}
int small = INT_MAX;
for (int i = 0; i < 8; ++i)
small = min(small, dist[xf][yf][i]);
if (small == INT_MAX)
g << "-1";
else
g << small;
}
int main()
{
read();
solve();
return 0;
}