// ----------------------------------------------------------------------------
#include <iostream>
#include <fstream>
// ----------------------------------------------------------------------------
using namespace std;
// ----------------------------------------------------------------------------
#define STERRING_DIRECTIONS 8
#define MAP_HEIGHT 500
#define MAP_WIDTH 500
#define WALL 1
#define ROAD 0
// ----------------------------------------------------------------------------
ifstream fin ("car.in");
ofstream fout ("car.out");
// ----------------------------------------------------------------------------
void change_direction (
unsigned DirectionIndex,
unsigned lNew,
unsigned cNew,
long LocalCost
);
void cautare (
unsigned lCurrent,
unsigned cCurrent,
unsigned TravelDirection,
long LocalCost
);
// ----------------------------------------------------------------------------
/**
+-----------------------------------------------------------+
| |
| |
| +--------+----------+ |
| | Degree | Cost | |
| +--------+----------+ |
| | 0 | 0 | |
| | 1 | 45 | |
| | 2 | 90 | |
| | 3 | 135 | |
| | 4 | 180 | |
| +--------+----------+ |
| |
| |
| +-----------------------+ |
| | Steering index | |
| +-----------------------+ |
| | | |
| | 3 2 1 | |
| | 4 0 | |
| | 5 6 7 | |
| | | |
| +-----------------------+ |
| |
| |
| +---------------------------+ |
| | Turning | |
| +---------------------------+ |
| | | |
| | 0 1 2 1 0 1 2 1 0 | |
| | 1 3 2 2 3 1 | |
| | 2 3 4 3 4 3 4 3 2 | |
| | | |
| | 1 2 3 3 2 1 | |
| | 0 4 4 0 | |
| | 1 2 3 3 2 1 | |
| | | |
| | 2 3 4 3 4 3 4 3 2 | |
| | 1 3 2 2 3 1 | |
| | 0 1 2 1 0 1 2 1 0 | |
| | | |
| +---------------------------+ |
| |
| |
| +---------------------------+ |
| | Steering cost | |
| +---------------------------+ |
| | | |
| | 0 1 2 1 0 1 2 1 0 | |
| | 1 3 2 2 3 1 | |
| | 2 3 4 3 4 3 4 3 2 | |
| | | |
| | 1 2 3 3 2 1 | |
| | 0 4 4 0 | |
| | 1 2 3 3 2 1 | |
| | | |
| | 2 3 4 3 4 3 4 3 2 | |
| | 1 3 2 2 3 1 | |
| | 0 1 2 1 0 1 2 1 0 | |
| | | |
| +---------------------------+ |
| |
| |
| +---------+---------------------------+ |
| | Cost | Steering index | |
| | of +------+------+------+------+ |
| | steering| 0 1 | 2 3 | 4 5 | 6 7 | |
| +-----+---+------+------+------+------+ |
| | | 0 | 0 1 | 2 3 | 4 3 | 2 1 | |
| | D | 1 | 1 0 | 1 2 | 3 4 | 3 2 | |
| | i +---+------+------+------+------+ |
| | r | 2 | 2 1 | 0 1 | 2 3 | 4 3 | |
| | e | 3 | 3 2 | 1 0 | 1 2 | 3 4 | |
| | c +---+------+------+------+------+ |
| | t | 4 | 4 3 | 2 1 | 0 1 | 2 3 | |
| | i | 5 | 3 4 | 3 2 | 1 0 | 1 2 | |
| | o +---+------+------+------+------+ |
| | n | 6 | 2 3 | 4 3 | 2 1 | 0 1 | |
| | | 7 | 1 2 | 3 4 | 3 2 | 1 0 | |
| +-----+---+------+------+------+------+ |
| |
| |
+-----------------------------------------------------------+
Cost [][] :
* Line : Direction of travel.
* Column : Steering index.
**/
int lSteering [8] = {0, -1, -1, -1, 0, 1, 1, 1};
int cSteering [8] = {1, 1, 0, -1, -1, -1, 0, 1};
/// Index 0 1 2 3 4 5 6 7
unsigned SteeringCost [8][8] = {
/* : 0 */{0, 1, 2, 3, 4, 3, 2, 1},
/* : 1 */{1, 0, 1, 2, 3, 4, 3, 2},
/* Direction : 2 */{2, 1, 0, 1, 2, 3, 4, 3},
/* : 3 */{3, 2, 1, 0, 1, 2, 3, 4},
/* index : 4 */{4, 3, 2, 1, 0, 1, 2, 3},
/* : 5 */{3, 4, 3, 2, 1, 0, 1, 2},
/* : 6 */{2, 3, 4, 3, 2, 1, 0, 1},
/* : 7 */{1, 2, 3, 4, 3, 2, 1, 0}};
/// Index 0 1 2 3 4 5 6 7
unsigned TravelOrder [8][8] = {
/* : 0 */{0, 1, 7, 2, 6, 3, 5, 4},
/* : 1 */{1, 0, 2, 3, 7, 4, 6, 5},
/* Direction : 2 */{2, 1, 3, 0, 4, 5, 7, 6},
/* : 3 */{3, 2, 4, 1, 5, 0, 6, 7},
/* index : 4 */{4, 3, 5, 2, 6, 1, 7, 0},
/* : 5 */{5, 4, 6, 3, 7, 0, 2, 1},
/* : 6 */{6, 5, 7, 0, 4, 1, 3, 4},
/* : 7 */{7, 0 , 6, 1, 5, 2, 4, 3}};
/// Index 0 1 2 3 4 5 6 7
unsigned Height, Width;
unsigned lStart, cStart;
unsigned lFinish, cFinish;
long CostMinim = -1;
int Harta [MAP_HEIGHT + 2][MAP_WIDTH + 2];
// ----------------------------------------------------------------------------
void change_direction (
unsigned DirectionIndex,
unsigned lNew,
unsigned cNew,
long LocalCost
)
{
if (Harta [lNew][cNew] == ROAD)
{
/// It's a road.
// So we don't end up in the same spot multiple times.
Harta [lNew][cNew] = WALL;
cautare(
lNew,
cNew,
DirectionIndex,
LocalCost
);
// Time to check another path.
Harta [lNew][cNew] = ROAD;
}
}
// ----------------------------------------------------------------------------
void cautare (
unsigned lCurrent,
unsigned cCurrent,
unsigned TravelDirection,
long LocalCost
)
{
if (-1 != CostMinim && LocalCost > CostMinim)
{
/// Wasting time here.
return;
}
if (lCurrent == lFinish && cCurrent == cFinish)
{
/// Arrived at destination.
if (CostMinim == -1 || CostMinim > LocalCost)
{
CostMinim = LocalCost;
}
} else {
/// Not there yet.
if (TravelDirection < STERRING_DIRECTIONS)
{
/// Already on the road.
for (unsigned TravelIndex = 0; TravelIndex < STERRING_DIRECTIONS; TravelIndex++)
{
unsigned DirectionIndex = TravelOrder[TravelDirection][TravelIndex];
unsigned lNew = lCurrent + lSteering [DirectionIndex];
unsigned cNew = cCurrent + cSteering [DirectionIndex];
if (Harta [lNew][cNew] == ROAD)
{
/// It's a road.
// So we don't end up in the same spot multiple times.
Harta [lNew][cNew] = WALL;
cautare (
lNew,
cNew,
DirectionIndex,
LocalCost + SteeringCost [TravelDirection][DirectionIndex]
);
// Time to check another path.
Harta [lNew][cNew] = ROAD;
}
}
} else {
/// At the start point.
for (unsigned DirectionIndex = 0; DirectionIndex < STERRING_DIRECTIONS; DirectionIndex++)
{
unsigned lNew = lCurrent + lSteering [DirectionIndex];
unsigned cNew = cCurrent + cSteering [DirectionIndex];
if (Harta [lNew][cNew] == ROAD)
{
/// It's a road.
// So we don't end up in the same spot multiple times.
Harta [lNew][cNew] = WALL;
cautare (
lNew,
cNew,
DirectionIndex,
LocalCost
);
// Time to check another path.
Harta [lNew][cNew] = ROAD;
}
}
}
}
}
// ----------------------------------------------------------------------------
int main(void)
{
unsigned iHeight, iWidth;
fin >> Height >> Width;
fin >> lStart >> cStart;
fin >> lFinish >> cFinish;
for (iHeight = 1; iHeight <= Height; iHeight++)
{
Harta [iHeight][0] = Harta [iHeight][Width + 1] = WALL;
for (iWidth = 1; iWidth <= Width; iWidth++)
{
fin >> Harta [iHeight][iWidth];
}
}
for (iWidth = 0; iWidth <= Width + 1; iWidth++)
{
Harta [0][iWidth] = Harta [Height + 1][iWidth] = WALL;
}
cautare(lStart, cStart, STERRING_DIRECTIONS + 10, 0);
fout << CostMinim;
fin.close ();
fout.close ();
return 0;
}
// ----------------------------------------------------------------------------
Daniel IliesiDaniel