Ten groźnie wyglądający algorytm sprawdza jedno pytanie: czy da się dojść z lewego górnego rogu do prawego dolnego, stąpając tylko po białych polach i ruszając się wyłącznie w prawo albo w dół.
Arkusz CKE — maj 2024, rozszerzony
Zasada — pole osiągalne, gdy białe i sąsiad osiągalny
Wyobraź sobie wodę nalewaną w lewym górnym rogu, która płynie tylko w prawo i w dół. Czarne pola to ścianki. Pytanie brzmi: czy woda dotrze do rogu na dole po prawej.
P[1][1] = (A[1][1] == 1)
for i in range(1, n+1):
for j in range(1, m+1):
if A[i][j] == 0:
P[i][j] = False # czarne = ściana
else:
gora = P[i-1][j] if i > 1 else False
lewo = P[i][j-1] if j > 1 else False
P[i][j] = (i == 1 and j == 1) or gora or lewo
# wynik: P[n][m]
To programowanie dynamiczne w czystej postaci — każde pole liczysz raz, na podstawie dwóch już policzonych sąsiadów.
Zadanie 1.1 — wyniki dla trzech plansz
| plansza | wynik |
|---|---|
| a) | PRAWDA |
| b) | FAŁSZ |
| c) | PRAWDA |
Nie analizuj planszy w głowie naraz. Wpisuj PRAWDA/FAŁSZ pole po polu, wiersz po wierszu od lewej, jak w sudoku. Jak dojdziesz do prawego dolnego rogu, masz odpowiedź. Minuta roboty.
Zadanie 1.2 — kontrprzykłady
a) plansza 5×5, najwyżej 2 czarne pola, wynik FAŁSZ
Zamaluj pole po prawej od startu i pole pod startem, czyli (1,2) i (2,1). Woda nie ma jak wypłynąć z rogu — oba wyjścia są zamurowane. Cała reszta planszy może być biała.
b) plansza 4×4, co najmniej 9 czarnych pól, wynik PRAWDA
Odwrotnie: zostaw białą jedną schodkową ścieżkę z rogu do rogu. Na planszy 4×4 ma ona 2·4 − 1 = 7 pól. Pozostałe 9 zamalowujesz. Ścieżka istnieje, więc PRAWDA, a czarnych jest dokładnie 9.
Zadanie 1.3 — ile czarnych pól zniesie PRAWDA
Żeby wynik był PRAWDA, musi istnieć biała ścieżka z rogu do rogu. Najkrótsza taka droga na planszy n×n to schodki odwiedzające 2n − 1 pól. Te muszą być białe, cała reszta może być czarna.
Odpowiedź: n² − (2n − 1) = (n−1)²
Sprawdzenie: dla 3×3 to 4, dla 5×5 to 16, dla 10×10 to 81.
Gdzie tracisz punkty
- Próba zablokowania planszy jednym polem. Pojedyncze czarne pole nigdy nie rozetnie planszy — wodę zawsze da się obejść. Najtańsze przecięcie to oba wyjścia z rogu naraz.
- Ruch w lewo albo w górę. Algorytm dopuszcza wyłącznie prawo i dół. Ścieżka „naokoło" nie istnieje, nawet jeśli wygląda na oczywistą.
- Pomylenie
2n−1z2n. Schodki z rogu do rogu na planszyn×nmają2n−1pól, bo pole startowe liczysz raz.
Ciekawostka
Liczba różnych schodkowych ścieżek z rogu do rogu (gdyby plansza była cała biała) na siatce n×m wynosi C(n+m−2, n−1) — czyli liczbę z trójkąta Pascala. Te same liczby wyskakują przy rozwinięciu (a+b)ᵏ i przy rachunku prawdopodobieństwa. Ścieżki kratowe, dwumian Newtona i trójkąt Pascala to dosłownie ta sama matematyka oglądana z trzech stron. Na maturze pytają tylko, czy jakaś ścieżka istnieje — ale pod spodem siedzi cała kombinatoryka.
Ten sam wzorzec w innych arkuszach
Skan siatki dwuwymiarowej i liczenie pola z już policzonych sąsiadów wraca regularnie:
- maj 2026, zad. 3 — pary słów — inny typ danych, ten sam nawyk „licz raz, zapamiętaj wynik"
- maj 2025, zad. 3 — Dron — geometria na liczbach całkowitych
Z tego samego arkusza: zad. 2 (Cyfry).
Programowanie dynamiczne brzmi groźnie, a w praktyce sprowadza się do „policz pole z dwóch sąsiadów". Rozpisane od zera w Variancie.
