WWO_01_18 - Znajdź ścieżkę

https://eduinf.waw.pl/inf/alg/001_search/0128.php29 na start

To jest wysoki poziom, ale wbrew pozorom - do ogarnięcia.

Odpowiada to skądinąd Twojemu rekurencyjnemu ifowi, tyle że jest znacznie szybsze.

Pomyśl nad tym w ten sposób. Jesteś w środku jakiegoś labiryntu. Mówimy o metryce Manhattan, ale na dłuższą metę - jeden pies. Ofc jak nie znasz pojęcia metryki to dowiedz się o co w tym chodzi - to akurat jest proste

Teraz jak chcesz wyjść z tego labiryntu? Masz nieograniczony czas na spacerowanie.

Najprostsza opcja to… sprawdzić wszystkie możliwe ścieżki - któraś w końcu doprowadzi do wyjścia!

Teraz jak to zrobić? Można rekurencyjnym ifem. Coś w rodzaju IF nie_udalo_mi_sie_wyjsc THEN szukaj_dalej(kolejna_pozycja). Ale z tym jest problem, np. labirynt może być taki:

#.#
.X.
#.#

X to Twoja pozycja, . - wolne miejsce, # - ściana. Twoja rekurencja musi to dobrze ogarnąć i zwiedzić KAŻDĄ możliwą trasę.

A gdyby tak wyobrazić sobie, że X to woda, która jak w Minecrafcie rozlewa się w każdym możliwym kierunku?

Robisz pętlę, która zapamiętuje gdzie wciąż “rozlewa się” woda. W chwili przedstawionej powyżej woda jest tylko w punkcie X. Potem interesuje Cię woda w miejscach kropek - bo tylko z tych kropek mogłaby ewentualnie pójść gdzieś dalej (X już sprawdziłeś).

I w zasadzie… tyle

Jak już napisałem, da się to zrobić rekurencją. Ale gdybyś tak pomyślał nad https://eduinf.waw.pl/inf/alg/001_search/0126.php7 ewentualnie https://eduinf.waw.pl/inf/alg/001_search/0125.php7 i https://en.wikipedia.org/wiki/Flood_fill4 to byłoby duuuużo prościej

PS pomyśl nad tymi labiryntami. Fajna zabawa; są nawet zawody w robieniu i kodowaniu robotów wychodzących z labiryntów. Sztuczki typu “trzymaj się lewą ręką ściany i idź a wyjdziesz z labiryntu” (choć tu musi być spełniony jeszcze jeden warunek; mniejsza).

PS 2 Swojego czasu kolega z wrk dał mi wydrukowany labirynt z jakiejś strony w necie na zasadzie “baw się młody”. Zeskanowałem go i napisałem program, który znalazł wyjście Zaszpanowałem

PS 3 W Minecrafcie jak wylejszesz wodę w miejscu X to po chwili rozleje się ona w miejsca oznaczone . . Pytanie czy dzieje się to faktycznie natychmiast czy tylko tak się wydaje osobie, która to widzi, a w rzeczywistości komputer zalewa najpierw jedną kropkę, potem drugą itd. Słowem: Ty możesz działać na piechotkę i zalewać kropkę po kropce. Jak sprawdzić, gdzie woda może się wlać, a gdzie nie? Ano sprawdzasz czy gdzieś jest . czy X czy #. Jak zapamiętać gdzie woda już się wlała? Ano ustawiając tam X - inaczej algorytm będzie się “cofał” i w końcu się zapętli. Jak zapamiętać, w których miejscach jest woda, która jeszcze gdzieś może się rozlać (to ważne! Nie możesz sprawdzać za każdym razem wszystkich X a jedynie te, które mają szansę się rozlać)? Polecam zaprzyjaźnić się chociażby ze stosem. Przyda Ci się znajomość STLa http://www.cplusplus.com/reference/stack/stack/3 .

PS 4 Nie rób wszystkiego co napisałem jednocześnie Zacznij od tablic (bo jakoś trzeba wczytać labirynt), postem STL (bo jest dużo przykładów na podanej stronie), potem zrozum o co chodzi w BFS i DFS (pamiętaj, że labirynt to też graf i każde pole łączy się ze swoimi 4 sąsiadami oraz wykonuj pomocnicze rysunki aż załapiesz. Ewentualnie jakaś wizualizacja na YT), potem zakoduj sprawdzanie czy z danego labiryntu da się w ogóle wyjść, a potem rozwiąż to konkretne zadanie

Powodzenia!

Testy:

In:

100
10
...#..#...
.##.#..#..
7
.#.#...
..#..#.
7
.#...#.
...##..
6
.#..#.
..##..
7
..##...
.#..#..
10
..##.#....
....#..##.
10
..#...#.#.
...#.#....
10
..#.#...#.
...#.###..
8
.#..#...
...#..#.
10
..#.....#.
...###.#..
8
.#..##..
..#...#.
7
.#.#.#.
..#.#..
9
..###..#.
.....##..
7
...#.#.
..#.#..
9
...#..##.
.##.#....
7
.##....
...#.#.
10
..##.#....
......#.#.
10
.##.#.....
...#..#.#.
8
..####..
.#....#.
7
....##.
.##....
9
.#.#...#.
....##...
6
..#.#.
.#.#..
10
......###.
.#.##.....
8
....#.#.
.#.#....
7
..#.#..
...#.#.
9
..###.#..
.#...#.#.
6
.##...
...##.
10
.#.....##.
...###....
10
....#...#.
...#..##..
8
.###....
.....##.
9
..#....#.
.....##..
8
.##.....
...###..
8
..#..#..
....#.#.
7
..###..
.#...#.
8
.#...#..
..##....
10
.#......#.
....####..
10
..##....#.
....##....
9
..#....#.
...####..
6
.#.#..
..#.#.
10
..#..#....
.#.#......
10
...#....#.
......##..
6
..#.#.
.#.#..
7
..#..#.
.#.#...
9
.##.#....
...#.##..
8
.#.##...
..#..#..
10
..##.###..
....#...#.
10
.#..#..#..
..##.#....
8
...#..#.
.#...#..
7
...#.#.
.##.#..
6
...##.
.##...
10
...#...#..
.##.....#.
7
..##.#.
.#..#..
9
....#.##.
.##......
10
...#...#..
.#...#..#.
9
....#.#..
.###.#.#.
9
...#.###.
.##.#....
8
..##.#..
.#....#.
6
.##...
...##.
9
.#..#....
..#....#.
6
.##...
...##.
10
..##..#...
.....#.##.
9
..###....
.#....#..
8
..#..#..
.#.##.#.
7
...#.#.
..#.#..
10
..#.#.....
...#..#.#.
9
...#.#...
.#..#.##.
10
.#...#....
......###.
10
.##....#..
....##..#.
6
..##..
.#..#.
10
.#.#......
..#.#.##..
9
.#....##.
..#..#...
9
......##.
.##......
10
.#####....
......##..
7
...##..
.#...#.
8
...#.#..
.##...#.
7
....##.
.##....
9
...#...#.
....###..
7
..##...
....##.
10
.....#..#.
..##..##..
10
.###.#..#.
....#.#...
9
..##..#..
.#.....#.
10
.#..#.....
..##..##..
8
.##.#...
...#..#.
10
....##....
......###.
10
.##..#....
....#.#.#.
10
.#...###..
..###...#.
10
.#...#....
..#...###.
8
.##.....
....##..
7
.#..#..
..#..#.
8
...#..#.
.#..#...
8
.#....#.
...##...
7
.##..#.
...##..
10
....#####.
.##.......
9
...##..#.
.#...#...
10
..##..#...
.....#..#.
8
..#.#.#.
.#.#.#..
7
...##..
.##....
7
...#.#.
.#..#..
10
...##.....
.#...#....
9
.#.#..##.
..#.#....

Out:

NIE
TAK
TAK
NIE
NIE
TAK
NIE
NIE
TAK
NIE
NIE
NIE
NIE
NIE
TAK
TAK
TAK
TAK
NIE
TAK
TAK
NIE
TAK
TAK
NIE
NIE
NIE
TAK
NIE
TAK
TAK
NIE
TAK
NIE
TAK
TAK
NIE
NIE
NIE
TAK
TAK
NIE
TAK
NIE
NIE
NIE
NIE
TAK
NIE
NIE
NIE
NIE
TAK
TAK
NIE
NIE
NIE
NIE
TAK
NIE
TAK
TAK
NIE
NIE
TAK
NIE
TAK
TAK
NIE
NIE
NIE
TAK
NIE
TAK
NIE
TAK
NIE
NIE
NIE
NIE
NIE
NIE
TAK
NIE
TAK
NIE
NIE
TAK
NIE
TAK
TAK
NIE
TAK
TAK
TAK
NIE
NIE
TAK
TAK
NIE

W końcu, po latach, miałem okazję wczytać się w to zadanie i je rozwiązać.

Z ciekawości rozważyłem tego “rekurencyjnego if’a” i faktycznie, zadanie da się rozwiązać bez ogólnej wiedzy o labiryntach. Trochę mnie to zaskoczyło - gdy widzę na SPOJu labirynt to defaultowo myślę flood fill. Jedynym wyjątkiem do tej pory było https://pl.spoj.com/problems/AL_26_08/3, choć i tak nie do końca.