BOOI 3 - Manalab
Уловието на задачата може да прочетете
тук.
Решение
Тази задача може лесно да се реши като
се изпробват всички възможни пътища между клетките s и f, и се изберат двата
които отговарят на условията. Това решение е твърде бавно и за W
и H > 5 няма да се вмести във времевото ограничение.
Съществува решение със сложност О(W2H2), основната идея на което е
да се представи лабиринтът като ориентиран претеглен мултиграф. Минималният
брой ходове се намира чрез обхождане в ширина, а минимално количество мана,
което трябва да се изхаби, се намира чрез алгоритъма на Дейкстра.
Лабиринтът се представя като граф по
следния начин: всеки връх има най-много по четири съседа -
отдолу, отгоре, отляво и
отдясно. С (i, j)-
(uk, vk) се означава път от клетка с координати (i, j)
до някоя от четирите й съседни (1 <= k <=
4). На всяка клетка от лабиринта в графа се съпоставя връх, а на всеки път
(i, j)-
(uk, vk) (когато в клетките (i, j) и (uk, vk) няма стена) -
ориентирано ребро с тегло, равно на маната, която ще
изхаби в клетка (uk, vk). Графът се представя чрез
матрица на съседство, като той ще има n
= W.H на брой върха. Остава да се намери функция, която да съпостави на
всяка клетка от лабиринта (i, j) уникален връх в графа. Върховете се
номерират последователно от горния ляв ъгъл до долния десен, като най-горе
вляво е числото 1, а най-долу вдясно е W.H. Така се определя функцията f(i,
j) = W.(i – 1) + j.
Нека v1 = f(i, j)
и v2 =
f(uk,
vk) и А е матрицата на съседство на графа. Възможни са следните случаи:
·
1. Ако някоя от клетките (i, j) или (uk, vk) е стена, то А[v1][v2] е безкрайност.
·
2. Ако в клетка (uk,
vk) се намира връх s или f, то А[v1][v2] е 0.
·
3. В останалите случаи за (uk, vk),
А[v1][v2] е количеството мана в
клетката (uk, vk).
Тъй като не може да се представи безкрайност
в компютъра, е достатъчно, когато между два върха няма ребро, стойноста на А[v1][v2] да е достатъчно голяма –
например 105.
По този начин настоящата задача се
свежда до една стандарта задача от теорията на графите. Първо се стартира
търсене в ширина от върха, означен с s,
дoкато се достигне този, означен с f,
като по този начин се намира най-късият по брой ходове път. След това чрез
алгоритъма на Дейкстра се намира минималния по количество изхабена мана път в
графа.
Примерна реализация
#include <stdio.h>
#define MAXWH 31
#define MAXN ( MAXWH * MAXWH )
#define MIN( a, b ) ( (a) < (b) ? (a) : (b) )
#define IN_AREA( x, y ) ( ( x >= 1 && x <= H ) && \
( y >= 1 && y <= W ) )
#define MAXVAL 1e5
#define DCOUNT 4
int map[MAXWH][MAXWH]; // the labirinth
int n, s_vert, f_vert, W, H;
int deltaI[DCOUNT] = { 1, 0, -1, 0 };
int deltaJ[DCOUNT] = { 0, 1, 0, -1 };
int A[MAXN][MAXN], T[MAXN];
int D[MAXN], prev[MAXN];
/* Breadth-first search */
void BFS( void )
{
int queue[MAXN], used[MAXN];
int vert, level, end, k, p, j;
for ( k = 0; k < n; k++ ) {
queue[k] = used[k] = 0;
prev[k] = -1;
}
queue[0] = s_vert;
used[s_vert] = 1;
vert = 0; level = end = 1;
while( vert < end ) {
for ( p = vert; p < level; p++ ) {
vert++;
if( queue[p] == f_vert ) return;
for( j = 0; j < n; j++ )
if ( ( A[queue[p]][j] != MAXVAL ) && !used[j] ) {
queue[end++] = j;
used[j] = 1;
prev[j] = queue[p];
}
}
level = end;
}
}
/* Finding the length of the longest path */
int pathLength( int j )
{
int count = 1;
if ( prev[j] > -1 )
count += pathLength( prev[j] );
return count;
}
/* Dijkstra algorithm */
void Dijkstra( void )
{
int i;
for( i = 0; i < n; i++ ) {
D[i] = A[s_vert][i];
T[i] = 1;
}
T[s_vert] = 0;
while ( 1 ) {
int j = -1, minDist = MAXVAL;
for( i = 0; i < n; i++ )
if ( T[i] && D[i] < minDist ) {
minDist = D[i];
j = i;
}
if ( j == -1 ) break;
T[j] = 0;
for( i = 0; i < n; i++ )
if( T[i] && ( A[j][i] != MAXVAL ) )
D[i] = MIN( D[i], D[j] + A[j][i] );
}
}
/* relates a vertex in the graph with a cell in the labirinth */
int vertex( int x, int y )
{
// f(x, y) - 1, because A is indexed beginning from 0
return ( W * ( x - 1 ) + y - 1 );
}
void readInput( void )
{
int i, j;
char str[MAXWH];
scanf( "%d %d", &W, &H );
for ( i = 1; i <= H; i++ ) {
scanf( "%s", str );
for ( j = 1; j <= W; j++ ) {
map[i][j] = str[j - 1];
if( map[i][j] == 's' )
s_vert = vertex( i, j ); // startov vryh
else if( map[i][j] == 'f' )
f_vert = vertex( i, j ); // kraen wryh
}
}
}
void initGraph( void )
{
int i, j;
n = W * H; // number of vertexes
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
A[i][j] = MAXVAL;
}
/* creating the graph */
void createGraph( void )
{
int i, j, k, di, dj, v1, v2;
char ch;
for( i = 1; i <= H; i++ )
for( j = 1; j <= W; j++ ) {
v1 = vertex( i, j );
for( k = 0; k < DCOUNT; k++ ) { // for every neightbour of (i, j)
di = i + deltaI[k];
dj = j + deltaJ[k];
if( IN_AREA( di, dj ) ) { // if is in the labirinth
v2 = vertex( di, dj );
if( map[i][j] == '#' || map[di][dj] == '#' )
A[v1][v2] = MAXVAL;
else {
ch = map[di][dj];
if( ch == 'f' || ch == 's' ) A[v1][v2] = 0;
else A[v1][v2] = ch - '0';
}
}
}
}
}
int main( void )
{
int verts, mana;
readInput();
initGraph();
createGraph();
BFS();
Dijkstra();
verts = pathLength( f_vert ) - 1;
mana = D[f_vert];
printf( "%d %d", verts, mana );
return 0;
}
Автор: Владимир Ангелов
обратно към текущ брой
|