Przeszukiwanie grafu w głąb (DFS)

01.10.2010 - Michał Karpiński
Trudność

Zadania ze sprawdzaczką

Implementacje DFS...
C, C++

Poniżej znajdują się proste zadania do napisania na komputerze. Każdy kto przeczytał niniejszy artykuł powinien bez problemu sobie z nimi poradzić.

Zadanie 1 - "Cykle"

Dla podanego grafu skierowanego sprawdź, czy zawiera on cykl.

Wejście

W pierwszym wierszu podana jest liczba naturalna N, która oznacza liczbę wierzchołków w grafie (wierzchołki numerujemy od 1 do N). W drugiej linii występuje liczba M - liczba krawędzi. W następnych M liniach podane są połączenia między wierzchołkami zapisane w postaci a b co oznacza, że istnieje krawędź z wierzchołka a do wierzchołka b.

Wyjście

Odpowiedzią ma być jedna linia z napisem TAK, jeśli w grafie istnieje cykl lub NIE w przeciwnym wypadku.

Przykład 1

Wejście:
3
3
1 2
2 3
3 1

Wyjście:
TAK

Przykład 2

Wejście:
5
5
1 2
1 3
1 4
4 5
5 2

Wyjście:
NIE

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Zadanie 2 - "Labirynt"

Sprawdź, czy można wyjść z labiryntu (czy istnieje droga z wejścia do wyjścia).

Wejście

Pierwsza linia wejścia zawiera dwie liczby N i M oddzielone spacją (gdzie 2 < N,M < 100). N oznacza wysokość, a M szerokość labiryntu. W kolejnych N wierszach opisany jest wygląd labiryntu z lotu ptaka. 'X' oznacza ścianę, a 'O' jest polem, po którym można się poruszać. 'S' oznacza pole startowe, a 'F' wyjście z labiryntu. Można się poruszać po labiryncie w pionie lub w poziomie. Podana mapa jest tak dobrana, że zawsze zawiera jeden 'F' i jeden 'S' oraz na bokach zawiera tylko ściany ('X'-y) lub ewentualnie 'F'-a/'S'-a.

Wyjście

Odpowiedzią ma być jedna linia z napisem TAK, jeśli istnieje wyjście z labirybtu lub NIE w przeciwnym wypadku.

Przykład 1

Wejście:
5 5
XFXXX
XOXOS
XOXOX
XOOOX
XXXXX

Wyjście:
TAK

Przykład 2

Wejście:
6 6
XXXXXX
XOOOOX
XOXXOX
XOSOOX
XOOXXX
XXXXXF

Wyjście:
NIE

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.272725
Twoja ocena: Brak Ocena: 4.3 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com