Zidine

pozz, ekipo!

Malo sam ostao bez ideja za ovaj zadatak, pa se nadam da ćete mi pomoći!

Evo linka: http://z-trening.com/submit.php?submit=7100136307&subm_code=1

pozz, Kinky.

Prvo bi trebao izracunati udaljenost izmedu kljuceva, a koliko vidim imas i gresku u bfsu, tj. u dijelu gdje ides po promjenama x i y kordinata.
Ti ides do N, a trebas ici do 4. Kada je izracunata udaljenost izmedu svih parova kljuceva, onda ti ostaje jedino da probas bilo koju permutaciju uzimanja kljuceva i nades najmanju...

Ovaj zadatak me stvarno iscrpio, evo koda, nadam se da ćete mi pomoć:

#include <algorithm>
#include <cstdio>
#include <cstring> 
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct koord {
       int x, y;
       koord ( int _x = 0, int _y = 0 ) {
             x = _x;
             y = _y;
       }
};

queue< koord > Q;
vector< koord > kljucevi;
int N, M, K;
char polje[ 51 ][ 51 ];
int pocx, pocy;
int udalj[ 11 ][ 11 ];
bool bio[ 51 ][ 51 ];
int dist[ 51 ][ 51 ];
int Udalj[ 51 ];
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
int take[ 101 ];
int Min = 10000;
int k;

void bfs ( int a, int b ) {
     memset ( dist, 0, sizeof ( dist ) );
     memset ( bio, 0, sizeof ( bio ) );
     Q.push ( koord ( a, b ) );
     while ( ! Q.empty() ) {
           koord pos = Q.front();
           Q.pop();
           for ( int i = 0 ; i < 4 ; ++i ) {
               koord dalje = koord ( pos.x + dx[ i ], pos.y + dy[ i ] );
               if ( dalje.x < 0 || dalje.x >= N || dalje.y < 0 || dalje.y >= M ) {
                  continue;
               }
               if ( polje[ dalje.x ][ dalje.y ] == '#' ) {
                  continue;
               }
               if ( !bio[ dalje.x ][ dalje.y ] ) {
                  bio[ dalje.x ][ dalje.y ] = 1;
                  dist[ dalje.x ][ dalje.y ] = dist[ pos.x ][ pos.y ] + 1;
                  Q.push ( dalje );
               }
           }
     }
}

void rek ( int lpos, int kljuc, int sec ) {
     if ( kljuc == k ) {
        if ( Min > sec && sec != 0 ) {
           Min = sec;
       
        }
        return;
     }
     if ( sec >= Min ) {
        return;
     }
     for ( int i = 0 ; i < k ; ++i ) {
         if ( ! take[ i ] ) {
            take[ i ] = 1;
            rek ( i, kljuc + 1, sec + Udalj[ i ] );
            take[ i ] = 0;
            rek ( i, kljuc + 1, sec + Udalj[ i ] );
         }
     }
}

int main() {
    scanf ( "%d %d %d", &N, &M, &K );
    for ( int i = 0 ; i < N ; ++i ) {
        scanf ( "%s", polje[ i ] );
    }
    for ( int i = 0 ; i < N ; ++i ) {
        for ( int j = 0 ; j < M ; ++j ) {
            if ( polje[ i ][ j ] == 'X' ) {
               pocx = i;
               pocy = j;
            }
            if ( polje[ i ][ j ] == 'K' ) {
               kljucevi.push_back ( koord ( i, j ) );
               ++k;
            }
        }
    }
    kljucevi.push_back ( koord ( pocx, pocy ) );
    ++k;
    for ( int i = 0 ; i < kljucevi.size() ; ++i ) {
        bfs ( kljucevi[ i ].x, kljucevi[ i ].y );
        for ( int j = i + 1 ; j < kljucevi.size() ; ++j ) {
            udalj[ i ][ j ] = dist[ kljucevi[ j ].x ][ kljucevi[ j ].y ];
        }
    }
    for ( int i = 0 ; i < k ; ++i ) {
        Udalj[ i ] = udalj[ kljucevi[ i ].x ][ kljucevi[ i ].y ];
    } 
    rek ( k, 0, 0 );
    printf ( "%d\n", Min );
return 0;
}