Текущ брой на Списание ИнфоМан
 


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;
}



Автор: Владимир Ангелов


обратно към текущ брой