wydaje mi się, że można oznaczyć drzwi jako wierzchołki i wtedy spróbować pokazać, że jest to graf co najmniej półhamiltonowski - czyli zastosować algorytm Robertsa-Floresa i zobaczyć, co dostaniemy ;] Tyle w ramach teoretycznego wstępu do formalnego rozwiązania :p
edit:
zdążyłem jeszcze sprawdzić, że wierzchołki mają stopnie od 7 do bodajże 12 w takim grafie, w związku z tym znajdą się takie dwa wierzchołki niesąsiednie, dla których suma ich stopni jest mniejsza
@ecco: Drzwi traktowałbym raczej jako krawędzie, a pokoje jako wierzchołki grafu. A kto zna twierdzenie Eulera, ten wie, czy zagadkę da się rozwiązać czy też nie. ;)
http://i40.tinypic.com/femnb8.jpg tutaj mamy graf obrazujący połączenia między pomieszczeniami i "terenem na zewnątrz". Liczymy ilość ścieżek wychodzących z wierzchołków grafu:
1 = 5
2 = 5
3 = 4
4 = 5
5 = 4
6 = 9
Warunkiem koniecznym dla posiadania drogi jednobieżnej przez graf jest, aby tylko dwa wierchołki miały nieparzystą ilość dróg wychodzących, reszta musi być parzysta. Warunkiem dla drogi Eulera (przechodzimy przez wszystkie drogi) jest,
Jeżeli masz jedno pomieszczenia (wierzcholek grafu) z nieparzystą ilością drzwi (połączeń), to trzeba zaczynać albo kończyć w tym pomieszczeniu.
Przy dwóch takich pomieszczeniach w jednym trzeba zacząć w drugim skończyć.
Przez każde pomieszczenie trzeba przejść N/2 dla parzystego lub (N-1)/2 dla nieparzystego gdzie N to ilość drzwi. Gdy przejdziemy wszystkie pomieszczenia z których możemy wyjść zostają nam tylko pojedyńcze wyjścia. Dwa pierwsze przypadki opisałem, gdy masz trzecie
Komentarze (309)
najlepsze
http://img188.imageshack.us/img188/2387/solution.png
Zastosowałem algorytm "poszukiwanie drogi do domu po sobotniej imprezie" opracowany przez zespół zdolnych polskich studentów ;)
http://img42.imageshack.us/img42/5812/rozwiazanie.jpg
Trailer.
do poczytania dla tych którzy lubią podobne zagadki
edit:
zdążyłem jeszcze sprawdzić, że wierzchołki mają stopnie od 7 do bodajże 12 w takim grafie, w związku z tym znajdą się takie dwa wierzchołki niesąsiednie, dla których suma ich stopni jest mniejsza
http://img190.imageshack.us/img190/5812/rozwiazanie.jpg
Zrobiłem tyle że białym kolorem może nie każdy zobaczy. U mnie widać
można tylko raz przechodzić przez drzwi ale nie jest powiedziane ile razy można przechodzić przez ściany...
sv_cheats 1
noclip
http://i40.tinypic.com/femnb8.jpg tutaj mamy graf obrazujący połączenia między pomieszczeniami i "terenem na zewnątrz". Liczymy ilość ścieżek wychodzących z wierzchołków grafu:
1 = 5
2 = 5
3 = 4
4 = 5
5 = 4
6 = 9
Warunkiem koniecznym dla posiadania drogi jednobieżnej przez graf jest, aby tylko dwa wierchołki miały nieparzystą ilość dróg wychodzących, reszta musi być parzysta. Warunkiem dla drogi Eulera (przechodzimy przez wszystkie drogi) jest,
Jeżeli masz jedno pomieszczenia (wierzcholek grafu) z nieparzystą ilością drzwi (połączeń), to trzeba zaczynać albo kończyć w tym pomieszczeniu.
Przy dwóch takich pomieszczeniach w jednym trzeba zacząć w drugim skończyć.
Przez każde pomieszczenie trzeba przejść N/2 dla parzystego lub (N-1)/2 dla nieparzystego gdzie N to ilość drzwi. Gdy przejdziemy wszystkie pomieszczenia z których możemy wyjść zostają nam tylko pojedyńcze wyjścia. Dwa pierwsze przypadki opisałem, gdy masz trzecie
BTW udowodni ktoś matematycznie, że się tego (z pokojami i drzwiami) nie da?