Planowanie potopu

04.06.2009

Z ankiety umieszczonej na forum wynika, że zadanie FLOODPLAN sprawiło wam najwięcej kłopotów. Nawet jeśli niektórzy wymyślili poprawne rozwiązanie, to nie udało im się go poprawnie zaimplementować. Tylko trzy osoby zrobiły to zadanie na 10 pkt.

Omówmy najpierw treść zadania. Dana była plansza z liczbami całkowitymi i należało "zalać" jej pewne pola stosując zasadę, że woda spływa w dół na wszystkie osiem pól sąsiadujących.

Zwykłe zalewanie pola (x,y) można zrealizować za pomocą przeszukiwania wszerz (ang. BFS), tzn. wkładając do pewnej kolejki Q sąsiadów zalewanego pola i pilnując aby nie włożyć do kolejki żadnego pola dwukrotnie:

1. h := wysokość pola (x,y);

2. wstaw (x,y) do kolejki Q

3. dopóki kolejka Q nie jest pusta wykonuj

3.1. weź z kolejki pole (a,b) // Q.front() , Q.pop()

3.2. wstaw do kolejki Q sąsiadów pola (a,b) o wysokości <= h

Liczba wyciągnięć z kolejki mówi nam ile zalaliśmy pól. Gdy okazuje się ona zbyt mała, tj. mniejsza od żadanej liczby zalanych pól, to należy w jakiś sposób znaleźć najniższe pole, którego nie dodaliśmy do kolejki (bo było zbyt wysokie). Oczywiście należy to zrobić szybko. Do tego służy inna kolejka - kopiec, albo kolejka priorytetowa.

Wyobraźmy sobie taką kolejkę, do której dołączają nowe elementy. Na przykład kolejkę do Media Markt w dwa dni przed otwarciem ;-) Jak to w życiu bywa taka kolejka nie jest zwykłą kolejką. Okazuje, że ktoś kto przyszedł później niż my może z jakiegoś powodu zacząć stać przed nami. To są właśnie priorytety :-)

W podobny sposób rozwiążemy zadanie "Planowanie potopu". Będziemy mieli kolejkę priorytetówą, w której priorytetem jest wysokość pola; ściślej, pole o niższej wysokości zawsze będzie w kolejce przed polem o wyższej wysokości. Gdyby powyższe rozwiązanie zmodyfikować w taki sposób, że wstawiamy do kolejki priorytetowej wszyskie osiem pól sąsiadujących z (a,b), nie zwracając uwagi na ich wysokość, to otrzymamy rozwiązanie, o ile zadbamy o to, aby żadnego pola nie wstawiać do kolejki dwukrotnie:

(x,y) - pole, z którego zaczynamy zalewanie

1. h := wysokość pola (x,y);

2. wstaw (x,y) do kopca Q;

3. ile := 0; // liczba zalanych pól

4. dopóki Q nie jest pusty wykonuj

4.1. weź z kopca pierwsze pole (a,b) // Q.front() , Q.pop()

4.2. jeśli wysokość pola (a,b) jest większa od h, to przerwij pętlę

4.3. ile++;

4.4. wstaw do kolejki Q wszystkich sąsiadów pola (a,b)

5. jeśli ile < k, to ustaw (x,y) na (a,b) (pole ostatnio wyciągnięte) i idź do kroku 1.

6. wypisz ile

Jedyne, co pozostaje, to implementacja kopca. Pozostawiamy to czytelnikowi, jako ciekawe ćwiczenie ;-). Myślę, że w portalu pojawią się notatki dotyczącę biblioteki STL, a w nich omówienie struktury priority_queue. Wobec tego kopca nie trzeba już pisać, lecz skorzystać z gotowego.

Rafał Nowak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com