Pagini recente » Cod sursa (job #2162443) | Cod sursa (job #2377761) | Cod sursa (job #757591) | Cod sursa (job #2325847) | Cod sursa (job #1146226)
#include <fstream>
#include <stack>
#include <string.h>
using namespace std;
const int Nmax = 505;
typedef pair<int, int> pi;
typedef pair<pi, int> ppi;
int bd[Nmax][Nmax];
int dist[8][Nmax][Nmax];
stack<ppi> S[3];
int dx[] = { 0,-1,-1,-1, 0, 1, 1, 1};
int dy[] = { 1, 1, 0,-1,-1,-1, 0, 1};
int main()
{
ifstream f ("car.in");
ofstream g ("car.out");
int N, M, sx, sy, fx, fy;
f >> N >> M;
f >> sx >> sy >> fx >> fy;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
f >> bd[i][j];
memset(dist, -1, sizeof(dist));
int cur = 0;
pi start {sx, sy};
for (int i = 0; i < 8; i++)
{
S[cur].push(make_pair(start, i));
dist[i][start.first][start.second] = 0;
}
int answer = -1;
while (!S[cur].empty())
{
bool done = false;
while (!S[cur].empty())
{
ppi pos = S[cur].top(); S[cur].pop();
int ax = pos.first.first,
ay = pos.first.second,
dir = pos.second,
d = dist[dir][ax][ay];
if (ax == fx && ay == fy)
{
answer = d;
done = 1; break;
}
// move ahead
int nx = ax + dx[dir],
ny = ay + dy[dir];
if (nx > 0 && nx <= N && ny > 0 && ny <= M && !bd[nx][ny]
&& (dist[dir][nx][ny] == -1 || dist[dir][nx][ny] > d))
{
dist[dir][nx][ny] = d;
S[cur].push(make_pair(make_pair(nx, ny), dir));
}
// turn 45-deg or 90-deg; left or right;
for (int sign = -1; sign <= 1; sign += 2)
for (int delta = 1; delta <= 2; delta++)
{
int newdir = (dir + 8 + sign*delta) & 7; // modulo 8
if (dist[newdir][ax][ay] == -1 || dist[newdir][ax][ay] > d + delta)
{
dist[newdir][ax][ay] = d + delta;
S[(cur + delta) % 3].push(make_pair(make_pair(ax, ay), newdir));
}
}
}
if (done) break;
else cur = (cur + 1) % 3;
}
g << answer << '\n';
return 0;
}