Pagini recente » Cod sursa (job #2151963) | Cod sursa (job #390378) | Cod sursa (job #1703453) | Cod sursa (job #1654661) | Cod sursa (job #1698902)
#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 };
int N, M, Si, Sj, Di, Dj, A[NMAX][NMAX], 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) % 8;
for (int k = 0; k < 5; k++)
{
i = (starti + k) % 8;
int complement = (i + 4) % 8;
if (current.x + di[i] < 1 || current.y + dj[i] < 1 || current.x + di[i] > N || current.y + dj[i] > M)
{
continue;
}
else
{
if (A[current.x + di[i]][current.y + dj[i]] == 0)
{
int diff = abs(complement - current.direction) % 4;
if (C[current.x][current.y][current.direction] + diff < C[current.x + di[i]][current.y + dj[i]][ (i + 4) % 8 ])
{
C[current.x + di[i]][current.y + dj[i]][(i + 4) % 8] = C[current.x][current.y][current.direction] + diff;
q.push(position(current.x + di[i], current.y + dj[i], complement));
}
}
}
}
}
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;
}