Pagini recente » Cod sursa (job #881137) | Cod sursa (job #893673)
Cod sursa(job #893673)
#include <fstream>
#include <algorithm>
#include <deque>
using namespace std;
const int D1[] = {-1, -1, 0, 1, 1, 1, 0, -1},
D2[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int INF = 0x3f3f3f3f;
int N, M, Si, Sj, Fi, Fj;
int A[502][502];
int minC[502][502][8];
deque<pair<pair<int, int>, int> > Q;
inline bool ok(int x, int y)
{
return x >= 1 && y >= 1 && x <= N && y <= M && !A[x][y];
}
int main()
{
ifstream fin("car.in");
ofstream fout("car.out");
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)
minC[i][j][k] = INF;
}
for (int k = 0; k < 8; ++k)
{
minC[Si][Sj][k] = 0;
Q.push_back(make_pair(make_pair(Si, Sj), k));
}
while (!Q.empty())
{
pair<int, int> now = Q.front().first;
int dir = Q.front().second;
Q.pop_front();
if (ok(now.first + D1[dir], now.second + D2[dir]) && minC[now.first][now.second][dir] < minC[now.first + D1[dir]][now.second + D2[dir]][dir])
{
Q.push_front(make_pair(make_pair(now.first + D1[dir], now.second + D2[dir]), dir));
minC[now.first + D1[dir]][now.second + D2[dir]][dir] = minC[now.first][now.second][dir];
}
int next1 = ((dir + 8) - 1) % 8, next2 = ((dir + 8) + 1) % 8;
if (minC[now.first][now.second][dir] + 1 < minC[now.first][now.second][next1])
{
if (minC[now.first][now.second][next1] == INF) Q.push_back(make_pair(now, next1));
minC[now.first][now.second][next1] = minC[now.first][now.second][dir] + 1;
}
if (minC[now.first][now.second][dir] + 1 < minC[now.first][now.second][next2])
{
if (minC[now.first][now.second][next2] == INF) Q.push_back(make_pair(now, next2));
minC[now.first][now.second][next2] = minC[now.first][now.second][dir] + 1;
}
}
int result = INF;
for (int k = 0; k < 8; ++k)
result = min(result, minC[Fi][Fj][k]);
if (result == INF) result = -1;
fout << result << '\n';
fin.close();
fout.close();
}