Pagini recente » Cod sursa (job #1069980) | Cod sursa (job #1951069) | Cod sursa (job #704955) | Cod sursa (job #1516085) | Cod sursa (job #903049)
Cod sursa(job #903049)
#include <fstream>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
#define INF 15000000
int m, n, dir[505][505][8];
bool a[505][505];
const int dx[] = {0, -1, -1, -1, 0, 1, 1, 1},
dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
struct coord {
int x, y;
} S, F;
queue <coord> Q[5];
coord init (int x, int y)
{
coord a;
a.x = x, a.y = y;
return a;
}
bool Check ()
{
for (int i = 0; i < 4; ++i)
if ((Q[i].front().x == F.x && Q[i].front().y == F.y))
return false;
if (Q[0].empty() && Q[1].empty() && Q[2].empty() && Q[3].empty())
return false;
return true;
}
void Way (coord C)
{
Q[0].push (C);
while (Check())
{
int u;
for ( u = 0; Q[u].empty(); ++u);
int i = Q[u].front().x;
int j = Q[u].front().y;
int M = INF, d = -1;
if (i == S.x && j == S.y)
M = 0;
else
for (int l = 0; l < 8; ++l)
if (dir[i][j][l] < M)
{
M = dir[i][j][l];
d = l;
}
for (int k = 0; k < 8; ++k)
{
int ii = i + dx[k];
int jj = j + dy[k];
int c = d == -1 ? 0 : (abs (k - d) < 4 ? abs (k - d) : 8 - abs (k - d));
if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj] && M + c < dir[ii][jj][k])
{
dir[ii][jj][k] = M + c;
Q[c].push (init (ii, jj));
}
}
Q[u].pop();
}
}
int main ()
{
ifstream fin ("car.in");
fin >> m >> n >> S.x >> S.y >> F.x >> F.y;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
{
fin >> a[i][j];
for (int k = 0; k < 8; ++k)
dir[i][j][k] = INF;
}
S.x--, S.y--, F.x--, F.y--;
for (int k = 0; k < 8; ++k)
dir[S.x][S.y][k] = 0;
fin.close();
ofstream fout ("car.out");
Way (S);
int M = INF;
for (int i = 0; i < 8; ++i)
M = min (M, dir[F.x][F.y][i]);
if (M != INF)
fout << M;
else
fout << "-1";
fout.close ();
return 0;
}