Pagini recente » Cod sursa (job #1359345) | Cod sursa (job #2141120) | Cod sursa (job #2572558) | Cod sursa (job #935317) | Cod sursa (job #2923622)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX = 505;
const int INF = 1e9;
int n, m, a[NMAX][NMAX], si, sj, fi, fj, sol;
int dp[NMAX][NMAX][10];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
struct el
{
int x, y, dir, cost;
};
queue<el> Q1, Q2;
bool ok(int i, int j)
{
if (i < 1 || j < 1 || n < i || m < j || a[i][j])
return false;
return true;
}
void citire()
{
el E;
fin >> n >> m;
fin >> si >> sj >> fi >> fj;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
fin >> a[i][j];
for (int k = 0; k < 8; k++)
{
dp[i][j][k] = INF;
}
}
}
for (int k = 0; k < 8; k++)
{
E.x = si;
E.y = sj;
E.cost = 0;
E.dir = k;
Q1.push(E);
}
}
void Dijkstra()
{
el E, W;
while (!Q1.empty())
{
while (!Q1.empty())
{
E = Q1.front();
Q1.pop();
W.cost = E.cost;
W.dir = E.dir;
W.x = E.x + dx[E.dir];
W.y = E.y + dy[E.dir];
if(ok(W.x, W.y) && dp[W.x][W.y][W.dir] > W.cost)
{
dp[W.x][W.y][W.dir] = W.cost;
Q1.push(W);
}
W.cost++;
W.dir = (E.dir + 1) % 8;
W.x = E.x;
W.y = E.y;
if(ok(W.x, W.y) && dp[W.x][W.y][W.dir] > W.cost)
{
dp[W.x][W.y][W.dir] = W.cost;
Q2.push(W);
}
W.dir = E.dir - 1;
if(W.dir < 0)
W.dir = 7;
if(ok(W.x, W.y) && dp[W.x][W.y][W.dir] > W.cost)
{
dp[W.x][W.y][W.dir] = W.cost;
Q2.push(W);
}
}
while (!Q2.empty())
{
E = Q2.front();
Q2.pop();
Q1.push(E);
}
}
}
void solve()
{
Dijkstra();
sol = dp[fi][fj][0];
for(int i = 1; i < 8; i++)
{
sol = min(sol, dp[fi][fj][i]);
}
if(sol == INF)
fout << -1;
else
fout << sol;
}
int main()
{
citire();
solve();
return 0;
}