Pagini recente » Cod sursa (job #2732288) | Cod sursa (job #2419687) | Cod sursa (job #900116) | Cod sursa (job #3211662) | Cod sursa (job #3226144)
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
const int NMAX = 505;
const int oo = 0x3f3f3f3f;
bitset<NMAX> a[NMAX];
struct car
{
int x, y, c, dir;
};
// cost[k][i][j] - costul minim pentru a ajunge in (i, j) cu directia k
int cost[8][NMAX][NMAX], mini = oo;
queue<car> q1, q2;
ifstream fin("car.in");
ofstream fout("car.out");
int n, m, t, sx, sy, fx, fy;
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
inline bool ok(car b)
{
return b.x && b.y && b.x <= n && b.y <= m && a[b.x][b.y] == 0;
}
int solve()
{
car u, v;
for (int i = 0; i < 8; ++i)
q1.push({sx, sy, 0, i});
while (!q1.empty())
{
while (!q1.empty())
{
u = q1.front();
q1.pop();
// nu schimbam directia deloc
v = u;
v.x += dx[v.dir];
v.y += dy[v.dir];
if (ok(v) && cost[v.dir][v.x][v.y] > v.c)
{
q1.push(v);
cost[v.dir][v.x][v.y] = v.c;
}
v = u;
// schimbam directia cu 45 de grade in sens trigonometric
++v.c;
++v.dir;
if (v.dir == 8)
v.dir = 0;
if (ok(v) && cost[v.dir][v.x][v.y] > v.c)
{
q2.push(v);
cost[v.dir][v.x][v.y] = v.c;
}
// schimbam directia cu 45 de grade in sens invers trigonometric
v.dir = u.dir - 1;
if (v.dir < 0)
v.dir = 7;
if (ok(v) && cost[v.dir][v.x][v.y] > v.c)
{
q2.push(v);
cost[v.dir][v.x][v.y] = v.c;
}
}
while (!q2.empty())
{
q1.push(q2.front());
q2.pop();
}
}
for (int i = 0; i < 8; ++i)
if (cost[i][fx][fy] < mini)
mini = cost[i][fx][fy];
if (mini == oo)
mini = -1;
return mini;
}
int main()
{
fin >> n >> m;
fin >> sx >> sy >> fx >> fy;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
fin >> t;
a[i][j] = t;
for (t = 0; t < 8; ++t)
cost[t][i][j] = oo;
}
if (a[sx][sy] == 1 || a[fx][fy] == 1)
{
fout << "-1\n";
return 0;
}
for (int i = 0; i < 8; ++i)
cost[i][sx][sy] = 0;
fout << solve() << "\n";
return 0;
}