Witam,
mam napisać program, który sprawdza czy labirynt ma wyjście.
Labirynt jest prezentowany przez tablice [10][10] o wejsciu w (0,0) i wyjsciu w (9,9)
Gdzie 'X' to ścianki a '0' to 'korytarz'
Czy jest jakiś prosty sposób , aby stwierdzić czy labirynt ma wyjście?
prosze o wskazówki
Poszukaj sobie algorytmu backtracingu, ew. klasyczny algorytm: idziesz zawsze z prawa reka dotykajaca sciany :)
Ślęcze nad tym algorytmem i wymyśliłem takie coś:
#include<iostream.h>
#include<string.h>
using namespace std;
int main()
{
int labirynt[11][11];
char lab;
string labir;
while(cin>>labir) //dopóki wczytuje labirynty
{
cout<<labir[0]<<endl; //wczytaj labirynt
int x=0,y=0;
for(x=0;x<10;x++) //wczytuje do tablicy labirynt ze stringa
{
for(y=0;y<10;y++)
{
if(labir[x*10+y]=='X')
{
labirynt[x][y]=1; //jesli sciana to 1
}
if(labir[x*10+y]=='O') //jesli korytarz to 0
{
labirynt[x][y]=0;
}
}
}
int poz=0,wiersz=0;
int iks=0,igrek=0;
while((iks!=9)&&(igrek!=9)) //dopóki nie jest na wyjsciu
{
if(igrek-1>-1)
{
if(labirynt[iks,igrek-1]==0)--igrek; //wprawo
}else if(iks+1<10)
{
if(labirynt[iks+1,igrek]==0)++iks; //front
}else if(igrek+1<10)
{
if(labirynt[iks,igrek+1]==0)++igrek; //w lewo
}else
{
cout<<'0'<<endl;break; /jesli brak wyjscia
}
}
cout<<'1'<<endl; //jesli jest wyjscie
}
return 0;
}
Ale nie działa [wstyd] </cpp>
Nie kumam za bardzo tego twojego wczytywania labiryntow :/ Wez wczytaj najpierw sensownie ten labirynt, albo wpisz go na razie na sztywno (do testow) i sprawdz najpierw czy na danej tablicy znajdzie wyjscie.
Z tekiej formy mam wczytać labirynty:
LAB 1: OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
LAB 2 OOOOOOOOOOXXXXXXXXXXOOOOOOOOOOXXXXXXXXXXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
Następnie zamieniam to sobie na tablicę 10 na 10. i tam gdzie jest X to zamieniam na 1 , a jak O to wypisuje 0.
Bardzo proszę o pomoc :(
Przyklad wczytania dla pliku
dane.txt
OOOOOOOOOOXXXXXXXXXXOOOOOOOOOOXXXXXXXXXXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
int labirynt[10][10];
//wczytanie
ifstream plik("dane.txt");
int i = -1;
while(!plik.eof() && ++i<100)
labirynt[i/10][i%10] = plik.get() == 'O' ? 0:1;
plik.close();
//sprawdzenie
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
cout << labirynt[i][j];
cout<<endl;
}
cin.get();
return 0;
}
Dzieki :)
teraz tylko zbadać czy ma wyjście dany labirynt.
Szczarze nie umiem tego, robie to chyba cały dzień i nic :(
bez rezultatów [wstyd]
No to tak jak mowilem. Dla malego labiryntu mozesz zrobic tak, jak z ta reka. Czyli zaczynasz od miejsca gdzie jest wejscie i posuwasz sie zawsze w prawo - w sensie punktu widzenia oczywiscie. Czyli cos takiego:
Proponuje na poczatek napisac sobie metody, ktore pomoga Ci obracac sie w prawo z jakiegos miejsca, robic krok naprzod, itp - tak, zeby to wszystko dzialo sie na tablicy i zapamietywalo aktualny 'punkt widzenia' - czyli obrot i miejsce przebywania.
Dla tak malego algorytmu moze nawet rekurencja być - wiem że to bardzo pamięć wcina ale na upartego.
Możesz w ten sposób zrobic to tak że 0 to ściana, 1 to ścieżka "dziewicza", a np 2 to ścieżka przebyta - jeśli bedziesz na swej drodze spotykał sciezke przebyta tzn że tą częśc labiryntu już przebyłeś możesz ją wyłaczyć z trasy i zacząć ruch od punktu gdzie spotkałeś się z przbyta scieżką ale juz nie mozesz tam wstąpić.
Ale ogólnie pomysl z prawą ręką mi się tez podoba. Powodzenia.
wpisz do komurki[0][0] liczbe 1
do każdej sąsiedniej (ale pustej) 2
i ak dalej
po zapełnienui całej tablicy wystarczy odszukać szereg 1...N
Ehh nie dosyć, że robisz ort'y to jeszcze nie rozumiesz tematu - my t szukamy najbardziej optymalnej metody znalezienia tego szeregu - lub samej a ty tylko napisałeś wystarczy znaleźć - ja w tablicy 10x10 to znajdziesz to spokojnie to w tablicy 10000x10000 już tak szybko ci to nie pójdzie.
Kiedyś pisałem taki program i był bardzo prosty.
Był on oparty na micie o Ariadnie i jej nici.
Miałem 2 struktury pomocnicze:
-tablicę wielkości labiryntu-pamietam w niej, czy dane pole już odwiedziłem. Na poczatku miejsca zajęte przez ściany zaznaczam jako odwiedzone.
-listę-nić-jej koniec jest zawsze w polu startowym, kiedy przesuwamy się o jedno pole, to wrzucamy to pole na początek listy(rozwijamy nić)
Wchodzimy tylko na pola na których jeszcze nie byliśmy. Nie ma znaczenia, czy będziemy chodzić w lewo czy prawo - jak bardzo chcemy, to przed każdym ruchem moglibyśmy losować kierunek.
Jezeli jesteśmy na polu, którego wszyscy sąsiedzi są zajęci, to "zwijamy" trochę nić i cofamy się o jedno pole.
Jeżeli jesteśmy na polu startowym i wszyscy sąsiedzi są odwiedzeni, to znaczy, że nie ma wyjścia.
P.S.
Jezeli ktoś nie zauważył, to ta lista działa jak stos
Można to też zrobić bez tablicy, ale działa dużo wolniej. W tym rozwiązaniu każde pole odwiedzimy co najwyżej raz(licząc cofanie się to dwa razy)
Na tym wlasnie o ile pamietam opiera sie metoda backtrackingu wlasnie, o ktorej pisalem wczesniej.