Czego się nauczysz
Nauczysz się przeszukiwać graf w głąb: rekurencyjnie i ze stosem, a na planszy zalewać obszar jak wiadro z farbą w programie graficznym.
Po co ci to na maturze
Zadania z mapą pytają np., jak duża jest wyspa albo do których miast da się dojechać z danego miejsca. Przeszukiwanie w głąb odpowiada na to, odwiedzając każde pole albo miasto jeden raz.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Jak najdalej, potem wróćIdziesz korytarzem do końca i cofasz się do ostatniego rozwidlenia.
- 1.2Wersja ze stosemTa sama myśl bez rekurencji: lista jako stos. Od przeszukiwania wszerz różni ją jedna metoda.
- 1.3Zalewanie obszaruWiadro z farbą: od klikniętego pola przez boki do wszystkich połączonych wolnych pól.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.