Po szachownoci n na m przechadza się król, ma ustalone pewne pole startowe i docelowe. Pewne pola są zabronione (znak '#'). Należy znaleźć jak najkrótszą ścieżkę dla króla.
Widać, że w zadaniu należy tylko wykonać algorytm BFS (przeszukiwanie wszerz). Problem polega na tym, jak rozsądnie reprezentować graf, a w szczególności krawędzie. Poniżej wszystkie możliwe przejścia obliczamy łatwo i przyjemnie, korzystając z tablic przesunięć dx, dy w możliwych ruchach króla, a także z funkcji sprawdzającej, czy po wykonaniu ruchu król nadal mieści się w danym wymiarze na planszy. Doświadczenie (moje) pokazuje, że tak najłatwiej uniknąć błędów wynikających z copy-paste'a lub na przykład z pomylenia wymiarów n i m. Dodatkowo, kolejka w algorytmie BFS jest reprezentowana w zwykłym wektorze, co także upraszcza kod (choć czasem może być nieefektywne pamięciowo).
int n,m;
char t[M][M];
vector<pair<int, int>> kol; // "kolejka"
int odl[1010][1010]; // wyniki
int dx[] = {1,1,1,0,0,-1,-1,-1};
int dy[] = {-1,0,1,-1,1,-1,0,1};
inline bool ins(int g, int h) { return g >= 0 && g < h; }
int bfs(pair<int, int> pocz, pair<int, int> kon) {
kol.push_back(pocz);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
odl[i][j] = INFTY;
odl[pocz.first][pocz.second] = 0;
for (int i = 0; i < (int)kol.size(); ++i) {
pair<int, int> q = kol[i];
for (int z = 0; z < 8; ++z) {
int a = q.first + dx[z], b = q.second + dy[z];
if (ins(a, n) && ins(b, m) && odl[a][b] >= INFTY && t[a][b] != '#') {
odl[a][b] = odl[q.first][q.second] + 1;
kol.push_back(make_pair(a, b));
}
}
}
return odl[kon.first][kon.second];
}
Zamiast tablic dx i dy można też użyć innej metody: przechodzimy pętlami po wszystkich możliwych parach przesunięć i piszemy warunek na to, kiedy dana para przesunięć jest dobra. Ta metoda dobrze uogólnia się na więcej wymiarów. Ale uważam tę metodę za błędogenną: swego czasu dzięki napisaniu niepoprawnego warunku udało mi się odpaść z Google Code Jam Europe 2005.
for (int i = 0; i < (int)kol.size(); ++i) {
pair<int, int> q = kol[i];
for (int dx = -1; dx <= 1; ++dx)
for (int dy = -1; dy <= 1; ++dy)
if (dx || dy) {
int a = q.first + dx, b = q.second + dy;
if (ins(a, n) && ins(b, m) && odl[a][b] >= INFTY && t[a][b] != '#') {
odl[a][b] = odl[q.first][q.second] + 1;
kol.push_back(make_pair(a, b));
}
}
}
Rozważamy łamigłówkę Rudy osioł (inna nazwa: Klotski), której zasady są opisane np. w tym artykule z Delty. Chcemy w jak najmniejszej liczbie ruchów dojść ze stanu początkowego do końcowego.
Zastosujemy znów algorytm BFS. Przede wszystkim należy przekonać się, że będzie odpowiednio niewiele stanów do przejrzenia. W podanym artykule znajdujemy oszacowanie, że będzie ich kilka milionów, czyli nie za dużo. Stany będziemy przenumerowywać, począwszy od jedynki, np. z użyciem mapy. Pozostaje pytanie, jakiej struktury użyć do reprezentacji stanu, tak aby można było łatwo przesuwać klocki.
Możemy ponumerować pola planszy (np. wierszami) liczbami od 0 do 19. Wtedy położenie danego klocka możemy zapisać jako maskę bitową pól, które on zajmuje (mask). Pamiętamy także wszystkie pola zajmowane przez jakikolwiek klocek (Mask). Wtedy przesunięcia klocka wykonujemy następująco. Lewo:
int maska_lewa = (1 << 4) * ((1 << 5) - 1); if (!(mask & (maska_lewa)) && !((Mask ^ mask) & (mask >> 1))) mask >>= 1;
Dół:
int maska_dolna = (1 << 20) - (1 << 16); if (!(mask & (maska_dolna)) && !((Mask ^ mask) & (mask << 4))) mask <<= 4;
Pozostałe kierunki podobnie. Musimy jeszcze zadbać o to, żeby cztery klocki o wymiarach 1 x 2 i cztery klocki 1 x 1 traktować jako nierozróżnialne. Jednym z możliwych sposobów jest pamiętanie masek bitowych wszystkich pól zajmowanych przez te dwa typy klocków. Warto zauważyć, że taką maskę możemy zawsze jednoznacznie odkodować. Czyli cała struktura może wyglądać np. tak:
struct stan {
int mask21, mask22; // pojedyncze klocki
int mask12, mask11; // wszystkie pola zajmowane przez te dwa typy klocków
};
Na prostokątnej planszy o wymiarach n na m nany pewne pola dostępne, a pewne zabronione. Chcemy pokryć tę planszę klockami o wymiarach 2 na 1 lub 1 na 2. Na ile sposobów możemy to zrobić? Znów, interesuje nas reszta z dzielenia wyniku przez jakąś niedużą liczbę całkowitą. Zakładamy, że n ≤ 15, m ≤ 100.
Mamy taką samą planszę jak w poprzednim zadaniu. Interesują nas cykle przechodzące przez wszystkie pole dostępne (przejść możemy tylko pomiędzy polami sąsiadującymi w pionie lub w poziomie). Znów chcemy wiedzieć, ile jest różnych takich cykli.
Interesuje nas szkic rozwiązania działającego w czasie O(2n * n2). Wskazówka: poprawne wyrażenia nawiasowe i liczby Catalana.
Zadanie domowe: zadanie Skoczek na ASD-SIO.