Pagini recente » Cod sursa (job #1689220) | Cod sursa (job #1018351) | Cod sursa (job #2900696) | Cod sursa (job #904542) | Cod sursa (job #3226143)
#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, dir;
};
// cost[k][i][j] - costul minim pentru a ajunge in (i, j) cu directia k
int cost[8][NMAX][NMAX], mini = oo;
deque<car> q;
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)
q.push_back({sx, sy, i});
while (!q.empty())
{
u = q.front();
q.pop_front();
// nu schimbam directia deloc
v = u;
v.x += dx[v.dir];
v.y += dy[v.dir];
int c = cost[u.dir][u.x][u.y];
if (ok(v) && cost[v.dir][v.x][v.y] > c)
{
q.push_front(v);
cost[v.dir][v.x][v.y] = c;
}
v = u;
// schimbam directia cu 45 de grade in sens trigonometric
++c;
++v.dir;
if (v.dir == 8)
v.dir = 0;
if (ok(v) && cost[v.dir][v.x][v.y] > c)
{
q.push_back(v);
cost[v.dir][v.x][v.y] = 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] > c)
{
q.push_back(v);
cost[v.dir][v.x][v.y] = c;
}
}
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;
}