Pagini recente » Cod sursa (job #2897664) | Cod sursa (job #1130109) | Cod sursa (job #358079) | Cod sursa (job #2738604) | Cod sursa (job #1698929)
#include <fstream>
#include <queue>
#define NMAX 501
using namespace std;
struct position
{
int x, y, direction;
position(int a, int b, int c)
{
x = a;
y = b;
direction = c;
}
};
int abs(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
int main()
{
const int INF = 1 << 30;
const int di[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
const int dj[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
bool A[NMAX][NMAX];
int N, M, Si, Sj, Di, Dj, C[NMAX][NMAX][8], i, j;
queue<position> q;
ifstream f("car.in");
f >> N >> M >> Si >> Sj >> Di >> Dj;
for (i = 1; i <= N; i++)
{
for (j = 1; j <= M; j++)
{
f >> A[i][j];
if (A[i][j] == 0)
{
for (int k = 0; k < 8; k++)
{
C[i][j][k] = INF;
}
}
}
}
f.close();
for (i = 0; i < 8; i++)
{
C[Si][Sj][i] = 0;
q.push(position(Si, Sj, i));
}
while (!q.empty())
{
position current = q.front();
q.pop();
int starti = current.direction < 2 ? current.direction + 6 : current.direction - 2;
for (int k = 0; k < 5; k++)
{
i = (starti + k) & 7;
if (A[current.x + di[i]][current.y + dj[i]] == 0)
{
int diff = abs(2 - k);
if (C[current.x][current.y][current.direction] + diff < C[current.x + di[i]][current.y + dj[i]][ i ])
{
C[current.x + di[i]][current.y + dj[i]][i] = C[current.x][current.y][current.direction] + diff;
q.push(position(current.x + di[i], current.y + dj[i], i));
}
}
}
}
int min = C[Di][Dj][0];
for (i = 1; i < 8; i++)
{
if (C[Di][Dj][i] < min)
{
min = C[Di][Dj][i];
}
}
if (min == INF)
{
min = -1;
}
ofstream g("car.out");
g << min;
g.close();
return 0;
}