Pagini recente » Cod sursa (job #2842180) | Cod sursa (job #2729390) | Cod sursa (job #1627681) | Cod sursa (job #1137681) | Cod sursa (job #930557)
Cod sursa(job #930557)
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 1<<20
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, d;
} S, F;
queue <coord> Q[2];
coord init (int x, int y, int d)
{
coord a;
a.x = x, a.y = y, a.d = d;
return a;
}
void Way ()
{
while (!(Q[0].empty() && Q[1].empty()))
{
int u;
for (u = 0; Q[u].empty(); ++u);
int i = Q[u].front().x;
int j = Q[u].front().y;
int d = Q[u].front().d;
for (int K = d + 7; K <= d + 9; ++K)
{
int k = K % 8;
int ii = i + dx[k];
int jj = j + dy[k];
int c = (K == d + 8) ? 0 : 1;
if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj] && dir[i][j][d] + c < dir[ii][jj][k])
{
dir[ii][jj][k] = dir[i][j][d] + c;
Q[c].push (init (ii, jj, k));
}
}
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;
Q[0].push (init (S.x, S.y, k));
}
fin.close();
ofstream fout ("car.out");
Way ();
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;
}