Pagini recente » Cod sursa (job #411072) | Cod sursa (job #2727430) | Cod sursa (job #1279750) | Cod sursa (job #2641040) | Cod sursa (job #902972)
Cod sursa(job #902972)
#include <fstream>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
#define INF 3000
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;
deque <coord> Q;
coord init (int x, int y)
{
coord a;
a.x = x, a.y = y;
return a;
}
void Way (coord C)
{
Q.push_back(C);
while (!(Q.front().x == F.x && Q.front().y == F.y) && !Q.empty())
{
int i = Q.front().x;
int j = Q.front().y;
int M = INF, d = -1;
Q.pop_front();
if (!(i == S.x && j == S.y))
for (int l = 0; l < 8; ++l)
{
if (dir[i][j][l] < M)
{
M = dir[i][j][l];
d = l;
}
}
else
M = 0;
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 && M + c < dir[ii][jj][k] && !a[ii][jj])
{
cout << i << " " << j << "(" << M << ") -> " << ii << " " << jj << " (" << M + c << ")\n";
dir[ii][jj][k] = M + c;
if (!c)
Q.push_front(init (ii,jj));
else
Q.push_back(init (ii, jj));
}
}
}
}
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;
}