Pagini recente » Cod sursa (job #2612510) | Cod sursa (job #1412303) | Cod sursa (job #3268287) | Cod sursa (job #3254276) | Cod sursa (job #902621)
Cod sursa(job #902621)
#include <fstream>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
#define INF 3000
int m, n, 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;
deque <coord> Q;
coord init (int x, int y, int d)
{
coord a;
a.x = x, a.y = y, a.d = d;
return a;
}
void Way (coord C)
{
Q.push_back (C);
while (!Q.empty())
{
int i = Q.front().x;
int j = Q.front().y;
int d = Q.front().d;
Q.pop_front();
for (int k = 0; k < 8; ++k)
{
int ii = i + dx[k];
int jj = j + dy[k];
int c = d == -1 ? 0 : (abs (d - k) < 4 ? abs (d - k) : 8 - abs (d - k));
if (ii >= 0 && jj >= 0 && ii < m && jj < n && a[i][j] + c < a[ii][jj])
{
a[ii][jj] = a[i][j] + c;
if (!c)
Q.push_front (init (ii, jj, k));
else
Q.push_back (init (ii, jj, k));
}
}
}
}
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)
{
int x;
fin >> x;
if (x == 1)
a[i][j] = -1;
else
a[i][j] = INF;
}
S.x--, S.y--, F.x--, F.y--;
a[S.x][S.y] = 0;
fin.close();
ofstream fout ("car.out");
S.d = -1;
Way (S);
/*for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
cout << a[i][j] << " ";
cout << "\n";
}*/
fout << (a[F.x][F.y] != INF ? a[F.x][F.y] : -1);
fout.close ();
return 0;
}